An odd thing happened today. I have version 21.4.1 on my laptop (a
PIII-1000, but only turned on a few hours a day so that LL tests would
take months) doing trial factoring. I ahppened to see the following in the
screen display tonight:
[Feb 13 01:44] Factoring M21632497 to 2^67 is 14.43%
AH yes... I recall when I was up there at about 120 on LL maybe better.
now someplace around 240 not sure i'll need to go look after this msg.
Even with 12 or so systems it still slips... the PC's , like me, are
getting old!!! On the factor side (slow old PC ) they just keep chewing
Well I've recently reached my 2nd GIMPS goal of getting into the
top 100 factoring. Last summer I made it to the top 1000 LL
testers and then switched from double checks to factoring to
make my mark there.
Now what to try for? :-)
Cheers... Russ
DIGITAL FREEDOM! --
pretty
close, relatively speaking...
Aaron
-Original Message-
From: [EMAIL PROTECTED]
[mailto:[EMAIL PROTECTED]] On Behalf Of
Russel Brooks
Sent: Tuesday, January 21, 2003 4:07 PM
To: [EMAIL PROTECTED]
Subject: Mersenne: Factoring Top 100
Well I've recently reached my 2nd GIMPS
At 12:07 AM 1/22/03 +, Russel Brooks wrote:
Well I've recently reached my 2nd GIMPS goal of getting into the
top 100 factoring. Last summer I made it to the top 1000 LL
testers and then switched from double checks to factoring to
make my mark there.
Now what to try for? :-)
Bah, top 100
Hi,
At 11:41 AM 2/12/2002 -0800, Aaron Blosser wrote:
PS - I'm just thrilled because I found a factor of an exponent that beat
my previous record... 101 bit factor. I'm too lazy to look through the
cleared exponents list, so does anyone know what the largest factor is
that has been found by
Hi,
At 09:18 PM 2/12/2002 +0100, Achim Passauer wrote:
And for all other readers all(?) factors with more than 99 bits which are
part of the latest cleared exponents report:
14308961 103 F 9394020965332917865679071542783
There are two minor shortcoming in the prime95 to primenet protocol.
I have a machine that was close to finishing its first factoring
assigment. It was 94.5% complete on the last (to 65 bits) pass. I
estimate the remainder would take about 3 to 4 hours to complete. I
started up a kids program for my son, he played with it for about 15
minutes and then exited.
Steve Harris wrote:
-Original Message-
From: [EMAIL PROTECTED] [EMAIL PROTECTED]
To: [EMAIL PROTECTED] [EMAIL PROTECTED]
Date: Tuesday, October 02, 2001 3:44 PM
Subject: Re: FW: Mersenne: Re: Factoring Failure?
snip
Either way, GIMPS
has never considered missing a factor as a big
Yesterday I was assigned M7027303 to doublecheck. The number came with the
claim that it had no factors less than 62 bits. But my P-1 factorization of
the number found this 55-bit factor:
[Sun Sep 30 13:53:26 2001]
P-1 found a factor in stage #1, B1=35000, B2=463750.
UID: dswanson/nosnawsd,
--- Forwarded message follows ---
From: Brian J. Beesley [EMAIL PROTECTED]
To: [EMAIL PROTECTED]
Date sent: Fri, 22 Jun 2001 18:46:43 -
Subject:Re: Mersenne: Factoring on a P4
Copies to: [EMAIL PROTECTED
For some reason, I am at a loss to explain, a v21 P4 1.4 GHz factors
significantely slower that a P3 v20 700MHz. Is there a reason, and solution,
for this?
Bradford J.
Brown
-
This message was sent using GSWeb Mail Services.
On 22 Jun 2001, at 13:12, [EMAIL PROTECTED] wrote:
For some reason, I am at a loss to explain, a v21 P4 1.4 GHz factors
significantely slower that a P3 v20 700MHz. Is there a reason, and
solution, for this?
Good question.
AFAIK George has done nothing to the factoring code. You will see a
BTW there was an unreasonable acceleration of trial factoring
between the P5 architecture (Pentium Classic/MMX) and the P6
architecture (Pentium Pro / PII / PIII / Celeron / Xeon), so you
can't simply assume that Intel doesn't care about integer
performance!
But they clearly don't care
Bradford J. Brown wrote:
For some reason, I am at a loss to explain, a v21 P4 1.4 GHz
factors significantely slower that a P3 v20 700MHz. Is there a
reason, and solution, for this?
Hmmm... Good question...
AFAIK, the only change George has or is going to make in the
factoring code since
Hi all,
I think I found a (although purely theoretical) way to find a factor of
M(p) by factoring M(M(p)).
Ok here goes:
f is a prime factor of M(M(p)),
2^(M(p)) = 1 (mod f)
so the order of 2 in Z/f*Z is !=1, divides M(p) but is not neccessarily
equal to M(p). Lets call it c.
Since the order
At 06:05 AM 3/4/01 -0800, Paul Leyland wrote:
Three weeks ago, I wrote:
The integer factoring people can always use more cycles, and
even antique machines make valuable contributions in a reasonable
time. For instance, I have small number of DECstations and a Sun
SS2 on my home network all
On 15 Dec 00, at 10:39, Henk Stokhorst wrote:
I spend the past months factoring the range 16.000.000 up to 17.000.000
form 2^52 up to 2^58. I reported the results once a week, which are
included in the database. This week someone else started to work on this
as well although up to 2^56. This
L.S.,
I spend the past months factoring the range 16.000.000 up to 17.000.000 form
2^52 up to 2^58. I reported the results once a week, which are included in the
database. This week someone else started to work on this as well although up
to 2^56. This work is therefor done twice. What is being
We could let prime95 decide the next election grin.
Give everybody a different prime number. Multiply the primes for
candidate A together, likewise for B.
And like in this election, unless we can completely factor
the results,
we wouldn't know who won, either.
:)
I note the
Paul Leyland wrote:
We could let prime95 decide the next election grin.
Give everybody a different prime number. Multiply the primes for
candidate A together, likewise for B.
And like in this election, unless we can completely factor
the results,
we wouldn't know who won,
The problem is for the government to factor the huge composite number
for each candidate afterwards. Can someone give me a rough
estimate of
how long it would take a good supercomputer to check an arbitrary
100,000,000 digit number for several factors that are each a known 150
digit
Hi folks,
Off-topic I know, but...
We could let prime95 decide the next election grin.
Give everybody a different prime number. Multiply the primes for
candidate A together, likewise for B.
And like in this election, unless we can completely factor the results,
we wouldn't know who won,
Chris Nash proposed:
We could let prime95 decide the next election grin.
Give everybody a different prime number. Multiply the primes for
candidate A together, likewise for B.
And like in this election, unless we can completely factor the results,
we wouldn't know who won, either.
From: Yann Forget [mailto:[EMAIL PROTECTED]]
Could you explain this to me ?
I can try. The text below is deliberately informal in style and far from
mathematically rigorous. The mathematicians on the list will have to
forgive me; those who want a more rigorous explanation should be able to
Stefan Struiker writes:
When a requested factoring assignment is listed with, say, 52 in an
account log, does this mean it has been factored to 52 bits, but
_without_ success?
Yes, the number should have no factors less than 2^52.
Or could a factor have already been found in some
Thanks for the factor.exe citation.
At 01:40 AM 6/16/00 -0700, Jim Howell wrote:
[Wed 14 Jun 2000, Paul Leyland writes]
Today I found this number 3756482676803749223044867243823 with ECM and
B1=10,000. It has two factors, each of 16 digits, which could *not* have
been found by trial division
At 01:00 PM 6/17/00 -0700, you wrote:
being found. Currently, all exponents thru Prime95's limit of
79.3M have been factored to at least 2^50... If a factor is
found for an exponent, it's eliminated from further testing
of any kind.
Isn't the factor itself verified?
From: Jeff Woods [EMAIL PROTECTED]
To: [EMAIL PROTECTED]
Subject: Re: Mersenne: Factoring Assignments: Are They Always
"First-Time?"
Date: Sat, 17 Jun 2000 17:14:00 -0400
At 01:00 PM 6/17/00 -0700, you wrote:
(snip)
If a factor is
found for an exponent, it's eliminated from furth
Jeff Woods wrote:
being found. Currently, all exponents thru Prime95's limit of
79.3M have been factored to at least 2^50... If a factor is
found for an exponent, it's eliminated from further testing
of any kind.
Isn't the factor itself verified?
Yes, it is. However, at least in the case of
[Wed 14 Jun 2000, Paul Leyland writes]
Today I found this number
3756482676803749223044867243823 with ECM andB1=10,000. It has two
factors, each of 16 digits, which could *not* havebeen found by trial
division in any reasonable time.
-
I use a program called "factor.exe", which
Hi,
Could you explain this to me ?
I am factoring Fermat numbers with ECM.
Is this relevant in this case ?
Thanks in advance,
Yann
Paul Leyland said:
As long as the coefficients of the curve and the starting point are
recorded, we can re-run exactly the same computation, with the small
primes
Brian Beesley (Mersenne Digest 715, 7. April) wrote:
There are also factoring programs available in portable
high-level-language source format, in particular look
for Mfactor.c If it wasn't for the fact that factoring
is so far ahead of LL testing, I'd probably switch my
Alpha system to
snipped a lot Note that Mfactor (as currently configured)
doesn't support putting multiple exponents into a to-do
file, so the best way to trial factor lots of exponents
is probably just to paste the one-line inputs needed for
the exponents, one after another, into the same window -
when the
Dave Mullen wrote:
I'd just like to get a clarification on some files I downloaded from the Entropia FTP.
Re the file of exponents, and how far they have been trial factored.
I extracted a range using the decomp program. Each exponent has a number by the side, but I am unclear to what this
I'd just like to get a clarification on some files
I downloaded from the Entropia FTP.
Re the file of exponents, and how far they have
been trial factored.
I extracted a range using the decomp program. Each
exponent has a number by the side, but I am unclear to what this number
refers.
PROTECTED]
An: [EMAIL PROTECTED]
Gesendet: Samstag, 22. Januar 2000 23:24
Betreff: Mersenne: Factoring beyond ECM
I'm interested in trying to factor composite numbers with 100 to 200
digits. ECM becomes impractical for numbers without any factors below
50 digits or so. I have heard
I'm interested in trying to factor composite numbers with 100 to 200
digits. ECM becomes impractical for numbers without any factors below
50 digits or so. I have heard of algorithms such as MPQS which are
used to tackle larger numbers. Are there any (preferably free)
implementations of this
On Sat, 22 Jan 2000, Foghorn Leghorn wrote:
I'm interested in trying to factor composite numbers with 100 to 200
digits. ECM becomes impractical for numbers without any factors below
50 digits or so. I have heard of algorithms such as MPQS which are
used to tackle larger numbers. Are there
On Sun, 23 Jan 2000 02:06:26 +0100 (CET), you wrote:
MPQS is ok for numbers up to about 100 digits, at which time NFS takes
over.
Is there a good implementation of this available online?
Have a look at Conrad Curry's NFSNET,
http://orca.st.usm.edu/~cwcurry/nfs/nfs.html
Foghorn Leghorn
[EMAIL
Hello!
I was fiddling around with Mersenne factors the other day and came across
an interesting result. I'm not sure if it is of any use, but I think if
anyone can extend it just a little further, then it would cut down the
numbers we would have to try to factor by a HUGE amount...
Anyway, any
Hi,
Ernst Mayer once mentioned to me that Prime95 needs twice the FFT size for 2^n+1
numbers (compared to 2^n+1 numbers). Does that mean that George is using the identity
2^(2n)-1 = (2^n+1)(2^n-1) ? I was wondering why ECM on 2^n+1 numbers took much longer
than on 2^n-1 of the same size..
That
On 3 Nov 99, at 13:53, Alex Kruppa wrote:
Ernst Mayer once mentioned to me that Prime95 needs twice the FFT size for 2^n+1
numbers (compared to 2^n+1 numbers). Does that mean that George is using the identity
2^(2n)-1 = (2^n+1)(2^n-1) ? I was wondering why ECM on 2^n+1 numbers took much
On Tue, 12 Oct 1999, Jukka Santala wrote:
Is it just me, or does factoring smaller Mersenne numbers take
propotionally much longer? I would expect M727 to be much faster than
the 33M range to a fixed depth, yet the opposite _seems_ to be true.
It's not just you, it's a natural consequence of
George Woltman wrote:
Since factors are of the form 2kp+1 there are many more factors to test
when you factoring M727. Yes each factor can be tested in less time,
but this is overwhelmed by extra factors to test.
Thanks to everybody pointing this one out, I missed the obivious
implication
"Brian J. Beesley" wrote:
// Regarding factoring Mersennes to v19 depth...
If you do decide to do this, you're on your own - don't be surprised
if someone else does the same thing independently - there's no
mechanism for coordination to avoid wasted effort.
Partially. There now exists
Jukka Santala wrote:
Is it just me, or does factoring smaller Mersenne numbers take
propotionally much longer? I would expect M727 to be much faster
than the 33M range to a fixed depth, yet the opposite _seems_ to
be true.
For any given factoring bit-depth, larger exponents will take
a shorter
Anyway, still waiting to hear if ECM will,
eventually, find all factors or if it leaves "factors" in the range...
The best way of thinking about this is that each curve at a given bound has
a small but non-zero probability of finding a factor of a certain length,
assuming that one exists.
Hi all,
At several users request I've uploaded factoring data for all exponents
below 79,300,000. You'll need a special decompression program I wrote.
See http://www.mersenne.org/status.htm for details.
Regards,
George
_
Does anybody know if there is an exponent where the
factor is, or know whether there is a proof on whether
a factor can (or can't) be, a root?? A square??
To clarify this:
We know that any factor of 2^p-1 is in the form 2kp+1.
Letting x =2,
Can (2kp+1)^x = 2^p-1 ??
Can (2kp+1)^x *
At 04:27 PM 9/21/99 -0700, Eric Hahn wrote:
We know that any factor of 2^p-1 is in the form 2kp+1.
Letting x =2,
Can (2kp+1)^x = 2^p-1 ??
Can (2kp+1)^x * (2kp+1) ... = 2^p-1 ??
No known factors of Mersenne numbers have x1, but it hasn't been proven
that it is impossible.
I was reading Fermat's Enigma today and something occurred to me...would it
be possible to work with a number quicker if we used a higher base? I.E.
Use base 32 instead of base 10? Thus, you're doing less math. Of course,
this would have to be in software because the floats can't be in that
At 01:10 PM 7/18/99 -0400, Geoffrey Faivre-Malloy wrote:
I was reading Fermat's Enigma today and something occurred to me...would it
be possible to work with a number quicker if we used a higher base? I.E.
Use base 32 instead of base 10?
Multiple precision arithmetic operations do that.
I may be a little obtuse here (and spelling, expression of ideas may be
inadequate) but
A Mersenne number's prime divisors are unique to that number. Letting a and
b be primes, 2^a - 1 and 2^b - 1 have completely different factors. So we
can make a table (database) with
p1 divides M(q1)
p2
Why test factor for primes in the range 2^1 to 2^10? If someone made the
table I described, it is possible that all primes less than 2^10 are in the
table I have described because they are known divisors of a Mersenne number
OR are not candidates for dividing any Mersenne number by other
Will change the "engine" to keep going to 2^33 after finding the
first factor report the results from that.
OK, here's the results. (All factors to 2^33 found, input is 159,975
largest primes 36 million)
Sieve 6 smallest primes, 3517525 calls, 40.15s
Sieve 10 smallest primes, 2972446
Brian J. Beesley writes:
I put a development version on my anon ftp server about three days
ago. ftp://lettuce.edsc.ulst.ac.uk/gimps/DecaMega/factor95.c
Um, that's an unfortunate choice of name; George's P-1 factorer is
"Factor95" (though there's a newer version, renamed to Factor98).
Well, looks like factoring on TI calculators won't be feasible or useful. :-(
Before more data comes in, I'd like to state that I believe three things:
A) The 38th Mersenne prime discovered has an exponent in the neighborhood of
6,900,000.
B) We *are* missing a Mersenne prime between 3021377
Chris Jefferson [EMAIL PROTECTED] writes:
Just one question / comment.
We want to find 2^p mod n where n is in form 2kp + 1
If we KNOW 2kp + 1 is prime, then the euler totient fn. of n is 2kp, call
this T
Also, if a is co-prime to n, a^T=1 mod n
2 is obviously co-prime to n, so 2^T=1
Now, this implies that for no 0N2kp, 2^N=1 mod (2kp + 1)
That depends on whether 2 is a primitive root of 2kp+1. If 2kp+1=11, p=5, 2 is
a primitive root and 2^p is -1. If 2kp+1=7, p=3, it isn't, and 2^p is 1.
phma
Unsubscribe
I was just wondering, could anyone give me any info on how factoring is
done, is there a preliminary factoring before numbers send out, how high
we factor, what possible factors are, etc. and also, I would really like
to see the maths behind it as well. I need something to study over summmer
vac
Sounds about right for a SWAG estimate.
SWAG?
SWAG stands for Scientific Wild-Assed Guess - translation: educated guess
-Lucas Wiman
Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm
Sorry if this has been mentioned before, but...
I was thinking (always dangerous!) about some of the smaller
Mersenne numbers, like 2^727-1, for which no factors are known.
2^727-1 has 219 digits, and we are pretty darn sure that it has no
prime factors less than 40 digits long. Therefore it
Earlier today I wrote:
In this case, there exist (large prime) integers a, b such that
(2 * a * n + 1) * (2 * b * n + 1) = 2^n - 1
A bit of rearrangement leads to the equation
2 * a * b * n^2 + (a + b) * n - 2^(n - 1) = 0
which it looks "feasible" to solve - yielding directly the two prime
At 02:48 PM 5/27/99 +, [EMAIL PROTECTED] wrote:
which it looks "feasible" to solve - yielding directly the two prime
factors of 2^n-1, assuming the assumption is correct.
Aaargh! The correct rearrangement is
2 * a * b * n^2 + (a + b) * n - (2^(n - 1) - 1) = 0
Doesn't affect the argument,
I was thinking (always dangerous!) about some of the smaller
Mersenne numbers, like 2^727-1, for which no factors are known.
2^727-1 has 219 digits, and we are pretty darn sure that it has no
prime factors less than 40 digits long. Therefore it would seem
sensible to "assume" that it is the
On Wed, 12 May 1999, Pierre Abbat wrote:
Is there a program for factoring numbers up to, say, 2^128 in a reasonable
time? I tried bc but it doesn't have a factor command, so I wrote a loop and it
spent all its time outputting.
Get Richard Crandall's giantint package, it contains factor, which
Hi all,
I haven't run prime95 the past year and I'm still among the
top ten producers. Well, last time I checked I was.
Didn't think I would last that long up there. ;-)
I was goofing around with perl today and recalled a cool
way of factoring/primality checking using patternmatching.
I also
[EMAIL PROTECTED] writes:
As LL tests begin to go beyond the limits of older machines, now may
be a good time to consider a distributed factoring effort. I've wanted
to see one for a while now but frankly, implementing many of the
algorithms is over my head. That, and the lack of a
Howdy,
I'm running PrimeNet on my 486sx/25 Linux router box (yeah, I know...). Right
now it's factoring M8956237, and it seems to do about one pass per day. It's
going to take a while. :)
Would adding a 487 math co-processor speed this up? If so, by how much? I
have no idea about the
Hi,
Last weekend when i was testing Prime 95 i noticed that factoring low
numbers took much longer as high numbers.
Factoring M17XXX from 2^52 to 2^54 took minutes per pass while factoring
M9XX from 2^52 to 2^54 took about one minute to complete the whole
factoring. How is this possible?
"Sander Hoogendoorn" [EMAIL PROTECTED] asks
Last weekend when i was testing Prime 95 i noticed that factoring low
numbers took much longer as high numbers.
Factoring M17XXX from 2^52 to 2^54 took minutes per pass while factoring
M9XX from 2^52 to 2^54 took about one minute to complete
Sander Hoogendoorn writes:
Last weekend when i was testing Prime 95 i noticed that factoring
low numbers took much longer as high numbers.
Factoring M17XXX from 2^52 to 2^54 took minutes per pass while
factoring M9XX from 2^52 to 2^54 took about one minute to
complete the
Sorry if this is a duplicate message. I am not sure if my previous attempt to
send this message got there or not.
Several months ago I downloaded fermat.exe from the Mersenne.org site
("zip file" at http://www.mersenne.org/fermat.htm). This program attempts
to find factors of Fermat numbers
Ok, George's programs looks for only for factors of M(n) in form
1) 2kn+1
that's clear why
2) 1,7,17,23,31,41,47,49,71,73,79,89,97,103,113,or 119 modulo 120
but this is not. Why factors 120k+13 are not considered? Or 120k+19? Why only those
16 reminders of
~30 primes below 120?
At 08:30 AM 1/12/99 -0500, Alexey Guzeev wrote:
Ok, George's programs looks for only for factors of M(n) in form
1) 2kn+1
that's clear why
2) 1,7,17,23,31,41,47,49,71,73,79,89,97,103,113,or 119 modulo 120
but this is not. Why factors 120k+13 are not considered? Or 120k+19? Why
only those
I wrote:
Henk Stokhorst writes:
table:1,7,17,23,31,41,47,49,71,73,79,89,97,103,113,119
In case it still isn't clear to someone out there, this is the list
of numbers less than 120 that are relatively prime (no common
factors greater than 1) to 120.
Oops! I should have
Henk Stokhorst writes:
table:1,7,17,23,31,41,47,49,71,73,79,89,97,103,113,119
In case it still isn't clear to someone out there, this is the list of
numbers less than 120 that are relatively prime (no common factors
greater than 1) to 120.
for number := first to last number in table do
78 matches
Mail list logo