Consider 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

miltbrown@...
----- Original Message -----

From: "Milton Brown" <miltbrown@...>

To: <primenumbers@yahoogroups.com>

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

> miltbrown@...

>

>

>

> [Non-text portions of this message have been removed]

>

>

>

> Unsubscribe by an email to: primenumbers-unsubscribe@egroups.com

> The Prime Pages : http://www.primepages.org

>

>

>

> Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/

>

>