Hello to all friends, how to code a prime factorization. Any simple explanation ?
Thanks for your help.
Printable View
Hello to all friends, how to code a prime factorization. Any simple explanation ?
Thanks for your help.
Google is your friend...plenty of good examples...plus the text book(s) from your classes may have some implementations, as this is often a problem in a first semester course.Quote:
Originally Posted by Peter_APIIT
My class does not covers this and google does not return any concrete result.
I just need a simple explanation.
Thanks.
4th hit on google. http://en.wikipedia.org/wiki/Prime_factor :rolleyes::rolleyes:Quote:
Originally Posted by Peter_APIIT
Anyone know Quadratic Sieve Algorithm ?
I did my research but i not understand the algorithm.
I have found this.
Why he say 38 to 98 in 2?Quote:
Quadratic Sieve factoring algorithm:
to factor n:
1. Select a set of prime numbers called the factor base.
(Selecting the factor base requires further explanation.)
2. For each integer f close to the square root of n,
try to factor (f^2)-n(mod n) with the primes in the factor base.
("Close to" is defined as an arbitrary range.)
3. If any or all of the primes in the factor base are factors
of (f^2)-n(mod n), save f.
4. Choose several of the saved f's such that when their squares
are multiplied together, the prime factors of the product(mod n)
all have even exponents.
5. Call the product of the f's x.
6. Call the square root of the product of the prime factors y.
7. Then, gcd(x+y, n) and gcd(x-y, n) are factors of n.
-----------------------------------------------------------------------------
Example:
to factor n=4633:
1. factor base = {2, 3, 5}
2. sqrt(4633) = 68.xxx, so f's "close to" 68 are, say, 38 to 98
3. For f's ((38, 98)^2) - 4633(mod n), the following have 2, 3 or 5
as prime factors: 59, 67, 68, 69, 85, 96
4. (68 * 69 * 96)^2(mod n) = 2^8 * 3^2 * 5^2 (the exponents are all even).
5. x = sqrt((68 * 69 * 96)^2(mod n));
y = sqrt(2^8 * 3^2 * 5^2)
6. x = (68 * 69 * 96) = 450432; y = ((2^4) * 3 * 5) = 240
7. gcd(450432+240, 4633) = 41; gcd(450432-240, 4633) = 113
8. 4633 = 41 * 113
I hope someone can clear myth.
Thanks.
Look at #2...Quote:
Originally Posted by Peter_APIIT
He picked 30 as the definition of "close". No mystery.Quote:
2. For each integer f close to the square root of n,
try to factor (f^2)-n(mod n) with the primes in the factor base.
("Close to" is defined as an arbitrary range.)