5054Fermat Factoring with First Digits
- Feb 2, 2002Consider Yan's RSA example on page 318
n = 63978486879527143858831415041
if you obtain the first 7 digits of each factor as
p = 1452951... and
q = 4403346... yielding
delta/2 = 1475197...
Spliting this value of k to 14751970...+ and 14751975...+
between two 1 gHz machines, enables the complete
factorization to be done on the second machine with
y = sqrt(21762078295163316989407257600)
to be done in 6.75 minutes.
(The notation corresponds to Yan's Fermat Factoring p. 198)
For anyone interested, I can provide additional documentation.
Contact me directly.
Milton L. Brown
----- Original Message -----
From: "Milton Brown" <miltbrown@...>
Cc: "Milton Brown" <miltbrown@...>
Sent: Friday, February 01, 2002 12:13 AM
Subject: [PrimeNumbers] Fermat Factoring with First Digits
> Fermat's Factoring Algorithm with the first digits of the
> factors known, can be done as on page 198 of Yan's book
> (Number Theory for Computing) with a different starting value of k
> k = Lower(Sqrt( n + (abc00...00)^2)) + 1
> where a, b, c are the known first digits and Lower means
> next smaller integer value.
> For his exercise 2.3.3 with n = 278153 (= 349*797)
> his k of 528 requires 45 steps, but with k = 565 requires
> only 8 steps. This is obtained with abc00...00 = 200
> where 200 = (700-300)/2.
> Milton L. Brown
> [Non-text portions of this message have been removed]
> Unsubscribe by an email to: email@example.com
> The Prime Pages : http://www.primepages.org
> Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/
- << Previous post in topic Next post in topic >>