Sorry, an error occurred while loading the content.

## 5054Fermat Factoring with First Digits

Expand Messages
• Feb 2, 2002
• 0 Attachment
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@...>
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/
>
>
• Show all 11 messages in this topic