RE: Mersenne: Hyperbola
From: Kris Garrett [mailto:[EMAIL PROTECTED]] I've noticed that with any odd number you can make the formula x^2 - y^2 = n where n = the odd number and x - y and x + y are factors of n. I was just wondering if one could use the graph of a hyperbola to see only the possible integer values of x and y. In effect, you've just described the basis behind many factoring algorithms. Fermat observed that if one could represent an integer as the difference of two squares, its factorization would be at hand; he then gave an efficient (for the 17th Century!) algorithm for finding the squares. More recently, algorithms such Continued Fraction, Quadratic Sieve and Number Field Sieve have all used Fermat's idea in the form x^2-y^2 = kN (k a small integer) or, equivalently, x^2 == y^2 (mod N) to factor N. The algorithms differ in how they construct the x and y and are *much* more efficient than Fermat's algorithm, but the underlying idea is the same. Paul Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Digest V1 #597
Mersenne DigestWednesday, July 14 1999Volume 01 : Number 597 -- Date: Mon, 12 Jul 1999 01:00:37 -0500 From: Ken Kriesel [EMAIL PROTECTED] Subject: Mersenne: re: Mersenne prime exponent binary representations and 1's frequency (incl M38) I said: The incidence of 1's in the second place from the right (excluding p=2) is 16/(16+21)=43.2%; This indicates the degree to which Mp for p=1 mod 4 is more probably prime than is p=3 mod 4. Of Mp for p=3 and up, p mod 4 # % 1 21 56.8 3 16 43.2 the incidence in the remaining interior bits is 172/358=48.0% This last line was wrong. For p=3, the second bit from the right is what I've been calling an exterior bit (most significant or least significant). So the one bit for p=3 should not be subtracted from either the one bit's count or the total bit positions counts for interior bits. So the correct incidence in remaining interior bits is 173/359~=48.2%. Credit for spotting this error goes to, who else, but George Woltman! George asks, what about the bit second from the left? In total, 26 0 bits vs only 12 1 bits. (0 26 of 38 times or ~68.4%; 26/12=2.1...) Excluding p=2 and p= 3, to look only at interior bits, 25 0 bits vs only 11 1 bits; 0 25 of 36 times, ~69.4%; 25/11=2.2727...) Now why would that be, that a 0 bit is more than twice as likely as a 1 bit? (Note that Mp#38, M6972593, has the less likely 1 bit in the second most significant position; searching biased for these probabilities would have delayed finding it. But the 4 previous Mersenne primes all had a 0 bit in that position.) Ken Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm -- Date: Mon, 12 Jul 1999 08:57:34 +0200 (MET DST) From: [EMAIL PROTECTED] Subject: Re: Mersenne: re: Mersenne prime exponent binary representations and 1's frequency (incl M38) Ken Kriesel [EMAIL PROTECTED] writes: George asks, what about the bit second from the left? In total, 26 0 bits vs only 12 1 bits. (0 26 of 38 times or ~68.4%; 26/12=2.1...) Excluding p=2 and p= 3, to look only at interior bits, 25 0 bits vs only 11 1 bits; 0 25 of 36 times, ~69.4%; 25/11=2.2727...) Now why would that be, that a 0 bit is more than twice as likely as a 1 bit? (Note that Mp#38, M6972593, has the less likely 1 bit in the second most significant position; searching biased for these probabilities would have delayed finding it. But the 4 previous Mersenne primes all had a 0 bit in that position.) The law of leading digits predicts that, for decimal numbers, log10(2) ~= 30.1% will have leading digit 1. More precisely, the fractional parts of the base-10 logarithms are assumed to be uniformly distributed. This distribution is invariant under many transformations, such as converting a physical constant from miles/hour to meters/second. For binary numbers, this predicts the leading bit is 1 with probability log2(2) = 1, a not surprising result. The two leading bits are 10 with probability log2(3) - log2(2) = ln(3/2)/ln(2) ~= 58.5%. This prediction is smaller than the observed 68.4%, but above 50%. Peter Montgomery Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm -- Date: Mon, 12 Jul 1999 09:21:40 -0400 From: Jeff Woods [EMAIL PROTECTED] Subject: Re: Mersenne: re: Mersenne prime exponent binary representations and 1's frequency (incl M38) At 08:57 AM 7/12/99 +0200, you wrote: The law of leading digits predicts that, for decimal numbers, log10(2) ~= 30.1% will have leading digit 1. Uh, won't they *ALL* have a leading digit of one? Anything with a leading digit of ZERO can be totally discounted Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm -- Date: Mon, 12 Jul 1999 09:24:56 -0400 From: Jud McCranie [EMAIL PROTECTED] Subject: Re: Mersenne: re: Mersenne prime exponent binary representations and1's frequency (incl M38) At 08:57 AM 7/12/99 +0200, [EMAIL PROTECTED] wrote: The law of leading digits predicts that, for decimal numbers, log10(2) ~= 30.1% will have leading digit 1. It depends on what set of numbers you are considering. +--+ | Jud "program first and think later" McCranie | +--+ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm -- Date: Mon, 12 Jul 1999 11:55:59 -0400 (EDT) From: Chip Lynch [EMAIL PROTECTED] Subject: Re: Mersenne: re: Mersenne prime exponent binary representations and 1's frequency (incl
RE: Mersenne: Hyperbola
From: Brian J. Beesley [mailto:[EMAIL PROTECTED]]
On 14 Jul 99, at 1:26, Paul Leyland wrote:
Fermat observed that if one could represent an integer as the difference
of
two squares, its factorization would be at hand; he then gave an
efficient
(for the 17th Century!) algorithm for finding the squares.
More recently, algorithms such Continued Fraction, Quadratic Sieve and
Number Field Sieve have all used Fermat's idea in the form x^2-y^2 = kN
(k a
small integer) or, equivalently, x^2 == y^2 (mod N) to factor N. The
algorithms differ in how they construct the x and y and are *much* more
efficient than Fermat's algorithm, but the underlying idea is the same.
Actually Fermat's Method is extraordinarily efficient at finding a
factorization n = a * b when (a - b) is small. It's also easy to
code, needs very little storage and (once initialized) requires only
relatively low-precision arithmetic, therefore making the attempt
fast (per iteration).
All of this is completely true, as long as the concept "small" is well
understood.
Fermat's method is excellent if (a-b) is about sqrt(a) or
sqrt(sqrt(N)). If it is much larger than this, Fermat's method is
hopelessly slow. In a "typical case", Fermat's method is slower than
trial division! "Typical" needs careful definition, of course. I
won't go into the assumptions and derivations, but in a "typical"
integer, successive factors (in numerical order) are about twice the
length of their predecessors. This means that (a-b) is far from
"small". A more rigorous formulation of this behaviour can be found
in standard texts, such as Knuth's Art of Computer Programming, Vol II.
This is one reason why it's a Very Bad Idea to use the product of a
pair of primes of similar size as a public key. In fact, Fermat's
Method will factorize the product of a pair of twin primes almost
instantaneously, irrespective of their size!
Indeed, if "similar" is interpreted as is "small" above. In a typical
case, a 512-bit key, the two primes will have about 78 digits each.
They have to be identical to the first 35-ish digits to be "similar".
If the primes are chosen randomly, the random number generator has to
be truly dreadful for that to happen by chance.
Just out of interest, did anyone ever try Fermat's Method on some of
the "tougher" numbers in the Cunningham tables ... Fermat's Method
can be speeded up by a large factor since we _know_ the form of the
factors - of course, it's still going to fail to find factors in a
reasonable time unless a pair of factors of very similar size do, in
fact, exist. Also, any factors found would not neccessarily be prime,
though cracking the two "halves" ought to be easier than tackling the
whole.
Not as far as I know, though some "similar" factors are known from
algebraic considerations. These are known as Aurifeuillean
factorizations. A simple example is
2^{2h} + 1 = (2^h-2^k+1) * (2^h+2^k+1) where h = 2k-1.
Paul
Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm
Mersenne: phew
Geez, just noticed my newest processor (a 2nd P2-400 added to a dual CPU mobo) got 3 LL exponents in the 7,993,000 range. 8 million is right around the corner, phew. So how far before we hit 64 bit and *really* get nailed for speed?? prime fact days exponent bits run / to go / exp date updated - --- 7993057 631.8 25.0 61.0 13-Jul-99 15:33 7993093 631.8 51.0 61.0 13-Jul-99 15:33 7993099 631.8 78.0 61.0 13-Jul-99 15:33 Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm
Development of Fermat's Method (was: RE: Mersenne: Hyperbola)
On 14 Jul 99, at 7:59, Paul Leyland wrote, in reply to my earlier message: Actually Fermat's Method is extraordinarily efficient at finding a factorization n = a * b when (a - b) is small. It's also easy to code, needs very little storage and (once initialized) requires only relatively low-precision arithmetic, therefore making the attempt fast (per iteration). All of this is completely true, as long as the concept "small" is well understood. Fermat's method is excellent if (a-b) is about sqrt(a) or sqrt(sqrt(N)). If it is much larger than this, Fermat's method is hopelessly slow. In a "typical case", Fermat's method is slower than trial division! I think you mean we want (a-b) to be _much_ smaller than sqrt(a) if Fermat's method is going to succeed reasonably quickly. However, ... Suppose we take a number which is proving troublesome to factorize, e.g. 2^727-1. Factors of this number are going to be of the form 1454k+1. The number is 219 decimal digits long; we are fairly sure, from work expended in ECM, that there are no factors much less than 45 digits long. Suppose we multiply 2^727-1 by 100!. The reason for doing this is that this just about guarantees that there is some combination of factors a, b such that (a-b) sqrt(a). Therefore we should be able to use Fermat's method (or anything else which might be better) and get a factorization in a reasonable time. We also know that none the factors of 2^727-1 are 100, so we can then reduce the factors found by dividing out of them all the primes 100. What we're left with must surely be the factorization of 2^727-1 (though the remaining factors might possibly still be composite). Now I'm not saying that the effort involved is trivial - I'm sure a run length of some hours, days or weeks would be neccessary. Also, I'd be very surprised indeed if I'm the first to suggest a trick like this, but, is it worth while starting to code this method? The point is that it's going to take a fair number of CPU years to complete ECM testing on 2^727-1 to the point where we're reasonably sure that there are no factors 10^50; for all we know, there might be only 2 factors each over 100 digits long, in which case ECM is almost certain to fail, unless _much_ faster hardware comes along. Regards Brian Beesley Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm
Re: Development of Fermat's Method (was: RE: Mersenne: Hyperbola)
Hi folks Suppose we take a number which is proving troublesome to factorize, e.g. 2^727-1. Factors of this number are going to be of the form 1454k+1. Suppose we multiply 2^727-1 by 100!. The reason for doing this is that this just about guarantees that there is some combination of factors a, b such that (a-b) sqrt(a) Now I'm not saying that the effort involved is trivial - I'm sure a run length of some hours, days or weeks would be neccessary. Also, I'd be very surprised indeed if I'm the first to suggest a trick like this, but, is it worth while starting to code this method? I can give a reasonably informed answer to this, having tried it myself. To use Fermat's method directly on kN in order to factor N, unless you are very lucky, is no improvement. In the 2^727-1 case, as pointed out, since you know the form of the factors, it's sufficient to try a=727x+1, for all a above sqrt(N), to check a^2-N is a perfect square. To preserve this, make the factor you multiply by a product of factors of the form 1454k+1 - all the factors of the product are still of this form. Do we win, or do we lose? Let's suppose that our composite has precisely two prime factors, and thus direct application of Fermat will uncover only one non-trivial solution from which we can derive the factor values. If what we multiply by has k distinct factors, then there are now 2^k useful solutions - but the number of values of a that we need to try has increased by more than that factor. In all likelihood, it would take longer... But don't despair. Since all we have to check for is "a^2-N is a perfect square", it's easy just to inspect this value modulo many small primes and sieve out quadratic non-residues. With a few lookup tables, it's easy to trial-factor at 10^9, even 10^12, values of a per CPU-second. Even so, for a 219-digit number like 2^727-1, and even assuming there's no factor below 40 or so digits, you'd still need 10^60 or more CPU-seconds to spare. (OK if you've got a universe with nothing else to do). Unsurprisingly, the method needs a bit of control to be realizable - which is what the continued fraction method achieves. Each iteration finds a (relatively) small square modulo N (at worst sqrt(N) in absolute value), which, after striking out square factors, making sensible choices of which to store, and judicious combinations, you hope to eventually find non-trivial a^2=b^2 mod N. Still need a lot of luck, though, and the steps are now non-trivial... Chris Nash Lexington KY UNITED STATES == Still a co-discoverer of the largest known *non*-Mersenne prime Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm
Re: Development of Fermat's Method (was: RE: Mersenne: Hyperbola)
Brian Beesley wrote: Suppose we multiply 2^727-1 by 100!. The reason for doing this is that this just about guarantees that there is some combination of factors a, b such that (a-b) sqrt(a). Therefore we should be able to use Fermat's method (or anything else which might be better) and get a factorization in a reasonable time. But the guarantee is not there. your a ~ sqrt(2^727 * 100!) ~ 10^188 sqrt(a) ~ 10^94 There are (only) 2^100 ~ 10^30 ways to choose the combinations of factors of 100! , which are the degrees of freedom. But they need to be chosen so that a-b 10^94 for a (and b) near 10^188. For f1, a factor of 2^727-1, near 10^100 it will be nearly impossible (not guaranteed) for (f1 * some combination of the factors of 100!) to be within one part in 10^94 of a certain number ~10^188. The combination of factors of 100! need to be within 10^-6 of a certain number of size ~ 10^88. 10^30 chances at hitting a number ~10^88 to within 10^-6 leaves you several dozen orders of magnitude short of a guarantee. Best regards, Todd Sauke Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm
Mersenne: subtracting 2: error in FAQ
All, I recieved a message pointing out a possible error in my FAQ: Speaking of Q2.6, I've heard that with Crandall's DWT, the subtraction 2 step costs nothing at all. It's done automatically within the transformation. Try checking this with George Woltman. Is this true? -Lucas Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm
Re: Mersenne: phew
Steinar H. Gunderson [EMAIL PROTECTED] replies to me... On Wed, Jul 14, 1999 at 09:28:08AM -0700, John R Pierce wrote: So how far before we hit 64 bit and *really* get nailed for speed?? You mean 64 bits of optimal factoring? Unless George comes up with something very smart (ie. a new factoring algorithm), I guess we will be stuck with 64 bits as optimal for a while, I'm afraid :-( Well, the current range of Mp candidate values (just under 8,000,000) is described as using a 63 bit 'factor'... I would assume eventually this has to go to 64 bits, but I'm not clear on the relationship between the exponent and the FFT size and the 'fact bits' listed on the test status pages. -jrp Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm
No Subject
Could someone show me a proof for(if there is one): The number 2^p-1 has factors in the form of 2pk+1 where k is any positive integer. _ Do You Yahoo!? Get your free @yahoo.com address at http://mail.yahoo.com Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm
Re: Mersenne: Proof of factor forms
Could someone show me a proof for(if there is one): The number 2^p-1 has factors in the form of 2pk+1 where k is any positive integer. try http://www.utm.edu/research/primes/notes/proofs/MerDiv.html -Lucas Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm
