Prime Factorization

[Peter_APIIT]

Hello to all friends, how to code a prime factorization. Any simple explanation ?

Thanks for your help.

[TheCPUWizard]

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.

[Peter_APIIT]

My class does not covers this and google does not return any concrete result.

I just need a simple explanation.

Thanks.

[TheCPUWizard]

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:

[Peter_APIIT]

Anyone know Quadratic Sieve Algorithm ?

[TheCPUWizard]

Anyone know Quadratic Sieve Algorithm ?

WHY do you refuse to do research???

Google (http://www.google.com/search?hl=en&q=Quadradic+Sieve&btnG=Google+Search&aq=f&oq=) provides immediate results (http://en.wikipedia.org/wiki/Quadratic_sieve).

[Peter_APIIT]

I did my research but i not understand the algorithm.

I have found this.


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


Why he say 38 to 98 in 2?

I hope someone can clear myth.
Thanks.

[TheCPUWizard]

I did my research but i not understand the algorithm.

I have found this.



Why he say 38 to 98 in 2?

I hope someone can clear myth.
Thanks.

Look at #2...

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.)


He picked 30 as the definition of "close". No mystery.