## Fermat Factoring with First Digits

Expand Messages
• 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
Message 1 of 11 , Feb 1, 2002
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]
• ... Anyone care to do a scan/upload so that we can see the full details? (Or transcribe) ... A where clause is usually intended to refine or clarify the
Message 2 of 11 , Feb 1, 2002
On Fri, 01 February 2002, "Milton Brown" wrote:
> 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)

Anyone care to do a scan/upload so that we can see the full details? (Or transcribe)

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

A 'where' clause is usually intended to refine or clarify the information we are already in poseesion of.
However, your 'where' clause explains the arbitrary selection of the number 200 in terms of an explanation which appears to have arbitrarily selected two numbers.

I did look for a possible justification, in the loosest sense of the word, for those _two_ numbers, and all I could see was that 300 is 349 truncated, and 700 is 797 truncated.

Does this mean that in order to help you find the factors more quickly, you need to know them, or their leading digits, in advance?

Shall we just say that I see a dog chasing its tail here, with the current description.

Phil

Don't be fooled, CRC Press are _not_ the good guys.
They've taken Wolfram's money - _don't_ give them yours.
http://mathworld.wolfram.com/erics_commentary.html

Find the best deals on the web at AltaVista Shopping!
http://www.shopping.altavista.com
• Phil: I think that Milton was here talking about how to use leading digits, not about how to find them. In this case he was suggesting how to make the very
Message 3 of 11 , Feb 1, 2002
Phil: I think that Milton was here talking about how to
In this case he was suggesting how to make the
very slow Fermat method slightly less slow, I guess?
Milton seems to specialize in messages where one has to guess.
David
• ... Milton s previous posts hav claimed that he can predict the leading digits. This has been called into question many times by the several people whose names
Message 4 of 11 , Feb 1, 2002
On Fri, 01 February 2002, "djbroadhurst" wrote:
> Phil: I think that Milton was here talking about how to

Milton's previous posts hav claimed that he can predict the leading digits. This has been called into question many times by the several people whose names all seem to begin with P. One particularly vociferous questioner has repeatedly requested a sketched algorithm, or at least some justification for the claims.

Milton posted what appeared to be part of an algorithm, with a cite too which was appreciated. My first guess was that it was trying to be the long awaited answer to the questions. However, as you say it could not be.

> In this case he was suggesting how to make the
> very slow Fermat method slightly less slow, I guess?

Haha, to be honest, if you throw a few trivial improvements into Fermat, it's not too shabby on the just-over-word-size range (where the mulmod methods start to require bignum maths vs. Fermat's adds and subs). Having said that Fermat did use some of these improvements himself, and thus didn't exactly use the technique which is presently called "Fermat's method".) Riesel demonstrates an extreme example of these trivial improvements in PNaCMfF, where the a >~12-digit number is split after one step!

Phil

Don't be fooled, CRC Press are _not_ the good guys.
They've taken Wolfram's money - _don't_ give them yours.
http://mathworld.wolfram.com/erics_commentary.html

Find the best deals on the web at AltaVista Shopping!
http://www.shopping.altavista.com
• ... To be even more fair to Fermat, it s a pretty good algorithm if you know that the composite has precisely two factors and that they differ only slightly in
Message 5 of 11 , Feb 1, 2002
> > In this case he was suggesting how to make the
> > very slow Fermat method slightly less slow, I guess?
>
> Haha, to be honest, if you throw a few trivial improvements
> into Fermat, it's not too shabby on the just-over-word-size

To be even more fair to Fermat, it's a pretty good algorithm if you know
that the composite has precisely two factors and that they differ only
slightly in size.

A case in point occurs in the 2-prime version of MPQS. Suppose a large
prime p lies in the range B1<p<B2 and a residue after dividing by factor
base primes (i.e all those <= B1) lies between max (B1^2, B2) and B2^2.
A fast pseudoprimality test tells us whether it's worth attempting to
factor the residue. In these circumstances, where B1 is typically
2^20and B2 is, say, 2^26 Fermat's method can be quite valuable.

I actually used Fermat for a while in PPMPQS, but we later found that
SQFOF almost always beat it.

Paul
• 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...
Message 6 of 11 , Feb 2, 2002
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/
>
>
• If you are more specific I will be glad to help. Thanks, Milton L. Brown miltbrown@earthlink.net ... From: Hugo Scolnik To: Milton Brown Sent: Sunday, February
Message 7 of 11 , Feb 3, 2002
If you are more specific I will be glad to help.

Thanks,

Milton L. Brown
miltbrown@...

----- Original Message -----
From: Hugo Scolnik
To: Milton Brown
Sent: Sunday, February 03, 2002 7:11 AM
Subject: Re: [PrimeNumbers] Fermat Factoring with First Digits

Dear Milton:

I am always interested in your findings but it seems I missed something crucial because your Excel files do not provide something to understand you.

Best

Hugo Scolnik

To ignore the facts does not change the facts

[Non-text portions of this message have been removed]
• ... I know I m not the only one to see the textbook irony in this situation. However, it seems that it matters no matter how specific people s questions are,
Message 8 of 11 , Feb 3, 2002
On Sun, 03 February 2002, "Milton Brown" wrote:
> If you are more specific I will be glad to help.

I know I'm not the only one to see the textbook irony in this situation.

However, it seems that it matters no matter how specific people's questions are, as you still seem utterly unable to answer them.

That's not strictly true. Last year, upon interested enquiry, you did give us some insight into your method. However, after you'd responded I'm sure at least four people independently warned you that the method you describe would be fruitless. Since then you've given us no evidence that your method has evolved in any way. Our conclusions are obvious...

Phil

Don't be fooled, CRC Press are _not_ the good guys.
They've taken Wolfram's money - _don't_ give them yours.
http://mathworld.wolfram.com/erics_commentary.html

Find the best deals on the web at AltaVista Shopping!
http://www.shopping.altavista.com
• ... ^^^^^^^^^^^^^^^^ [snip] ... This requires knowing _how_many_digits_ are in \$b and \$a, not just the leading ones. (I m sure others have noticed this, but I
Message 9 of 11 , Feb 3, 2002
Milton Brown wrote:

>The algorithm is from page 198 of Yan's book, reproduced below
>I just modified it to start with a different value of k based on knowing
>the first digits of the two factors:
^^^^^^^^^^^^^^^^

[snip]

>I have implemented this, and used k <= lower(sqrt(n+(b-a)^2))+1
^^^
>where b = b1 b2 b3 ... 000 first digits of larger factor
^^^^^^^
>and a = a1 a2 a3 ... 000 first digits of smaller factor.
^^^^^^^
>This is much faster, and faster with the more first digits you know.

This requires knowing _how_many_digits_ are in \$b and \$a, not just
the leading ones. (I'm sure others have noticed this, but I don't
recall anyone pointing it out.)

If Milton's Method provides this essential info, then why not iterate
it in a sequence of well-chosen bases, rather than just 10. (This
was abortively suggested in connection with the CRT, AFAIR.)

IF the previous condition holds, you could choose a base such that a
power of it was about in the middle of the range for one of \$a or \$b
constrained by all previous iterations and find the number of digits
in that base (and maybe some of the leading ones, but that would be
a bonus).

THEN you would have a factorisation algorithm that approximated a
binary search, i.e. O(log(N)). That would be a breakthrough ;-)
(You could use approximate logs to avoid too much faffing about.)

Why do I think that the Milton Method probably falls down here?

I would LOVE to be wrong.

Andy
• Thanks, Milton, for indicating how you might use ... So _if_ you knew the first 10 digits of the factors of RSA-576, as you claimed in
Message 10 of 11 , Feb 3, 2002
Thanks, Milton, for indicating how you might use
(as opposed to determine) leading digits of factors:

> I just modified it [Fermat] to start with a different value
> of k based on knowing the first digits of the two factors

So _if_ you knew the first 10 digits
of the factors of RSA-576, as you claimed in

or maybe even the first 15, as you later claimed,
what good would it do you?

Could you please tell us the number of Fermat tests
that you would then need to do, and also compare it with
the number of femtoseconds since the universe began?

David
• Andy: I believe that Milton is assuming that both factors of RSA-576 have equal number of decimal digits, and also claiming that he knows the first 15 of each.
Message 11 of 11 , Feb 3, 2002
Andy: I believe that Milton is assuming that
both factors of RSA-576 have equal number of decimal
digits, and also claiming that he knows the first 15 of each.
Such info would then be base-independent
(yet still worth sweet-Fanny-Adams in a Fermat method)
David
Your message has been successfully submitted and would be delivered to recipients shortly.