Hi,
I saw code posted earlier today that did LL testing with the GMP
library. It used the mpz_powm_ui function for exponentiating modulo x.
For x=2**p-1 this function can be sped up considerably, since
a mod (2^p-1) = a % 2^p + a / 2^p (integer operations) and these can
be done by bit shifting/ma
Hi,
I´m thinking about something the would probably be called a stage 2 for
my P-1 factorer, i.e. the 3^(E*(p+x)) = 3^(E*p) * 3^(E+x) with x
difference between subsequent primes.
But I need to check for a factor after every of these steps, and a
full-blown GCD would be far too slow. Is there anot
Morten Due Jorgensen wrote:
>Given two programs, one running at normal priority, the other at the
>lowest possible priority (idle priority), the second program will get
>around 1-2% of the CPU,
I noticed the same thing under Linux (with rc5des). Idle processes get a
few % cpu time even on per
Hi,
I just tried a quick run of Georges new P-1 code on M(M(17)), and lo!
[cut]
At prime 499549. Time thusfar 1707.604 sec. (341520836670 clocks)
Stage 1 complete. 365804 transforms. Time: 1717.294 sec. (343458751180
clocks)
Stage 1 GCD complete. Time: 19.737 sec. (3947333454 clocks)
M131071 ha
Alexander Kruppa wrote:
>
> Hi,
>
> M131071 has a factor: 14899621191992882743
>
> That wan't hard. But one thing puzzles me:
>
> P-1 = 2*3*61*6229*131071*49861943
>
> The factor was found after stage 1 with a limit of 50 - how can it
> find a fact
Robert van der Peijl wrote:
>
> He further writes:
> There are some Linux folks that like the present program because it
> doesn't use X-windows.
I certainly do! A program like mprime that is supposed to run in
background at all times should not depend on a X server running. Maybe
the setup
Hello all,
a simple Number Theory question. Is always
(2^p-1) / p ,odd prime p, divisible by 3 ?
Then 2^p == 1 (mod 3p) would also hold, can this be used to improve the
efficiency of a Rabin-Miller probable prime test?
Ciao,
Alex.
_
"Vincent J. Mooney Jr." wrote:
>
> 5 is an odd prime. 2^5 = 32 and minus one, is 31. 31 is not divisible by 3.
>
>
> At 07:50 PM 10/26/99 +0200, you wrote:
> >Hello all,
> >
> >a simple Number Theory question. Is always
> >
> >(2^p-1) / p ,odd prime p, divisible by 3 ?
> >
Well, I managed to
Hi,
the Lucas-Lehmer iteration
L_0 = 4
L_{n+1} = L_n ^2 -2
looks suspiciously like an iteration used in Pollard-Rho:
x_0 = a
x_{n+1} = x_n ^2 +b
Can this be used to do a LL test and Pollard-rho factoring attempt at
once?
I remember faintly having read something that b=-2 is not a good choice
Eric Hahn wrote:
>
> I'm looking for program(s) capable of trial-factoring
> prime exponent Mersenne numbers (using 2kp+1) meeting
> the following requirements:
>
> [factors and exponents of arbitrary size]
>
mersfacgmp from the Will Edgingtons mers package uses gmp's mpz type for
factors (thus
Jason Stratos Papadopoulos wrote:
>
> On Thu, 28 Oct 1999, Alexander Kruppa wrote:
>
> > Hi,
> >
> > the Lucas-Lehmer iteration [...]
> > looks suspiciously like an iteration used in Pollard-Rho: [...]
> > Can this be used to do a LL test and Po
Gordon Spence wrote:
>
> So how do we get to beg, borrow or steal time on this monster...
>
> http://www.pcworld.com/pcwtoday/article/0,1510,14151,00.html
If they need code for a test drive, I could make a suggestion here..
hey, if David can do it..
Ciao,
Alex.
__
Stefan Struiker wrote:
>
> Olivier Langlois wrote:
>
> > alternative. "As far as I am concerned, the value of pi is only a theory,
> > and we should be open to all interpretations." She looks forward to the
> I think it is meant as a spoof on the still-current controversy over
> giving both c
Jeff Woods wrote:
>
> Dave has at least 80 exponents reserved between 2.4M and
> 3.99M. Eighty. Almost all are less than suspected M37. It is a
> certainty that without poaching, we will have to wait until late 2000 or
> later to prove M37, because Dave is trying to do all the double-check
>www.mersenne.org/ecmg.htm for current ECM factoring limits on Fermat numbers,
Oops, should read: ecmf.htm
Ciao,
Alex.
_
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ -- http://www.tasam.
Nayan Hajratwala wrote:
>
> problem; I need to find the largest known prime of the form:
> (2^2^n)+1
> congratulations by the way on finding the largest Mersenne prime!!!
These are Fermat numbers, Fermat conjectured that all numbers of this form
would be prime and proved it for
F
"Robert G. Wilson v" wrote:
> Yes it is. In fact there are five numbers with this
> characteristic. (10^n -1)/9 is prime when n is 2, 19, 23, 317 & 1031.
> See "The Encyclopedia of Integer Sequences" sequence M2114, Neil J.A.
> Sloane and Simon Plouffe, Academic Press, 1995.
>
Are all
Hi all,
I've been trying to figure out what the chance of finding a P-1 factor
is, given a certain amount of trial factoring and a P-1 bound.
I started with:
The chance of Mp having a factor in [2^n, 2^(n+1)] is 1/n.
The chance of a number N being B-smooth is
(log(B)/log(N))^(log(N)/log(B)) .
S
Spike Jones wrote:
> Ask yourself: Do I *know*
> more about math now than when I started GIMPS?
You can say that again. I remember well when I asked on the list what the
point of P-1 factoring is when it takes an hour to get to 100 (or
103, rather) while trial factoring can do 2^40 in t
George Woltman wrote:
> Correct. However, if you do find a factor you will get credit. In fact
> you get credit for trial factoring up to the size of the factor.
Umm.. I found some 30-digit factors with moderate bounds. Does that mean I'd get
credit for trial-factoring up to 100 bits? Trial fa
Paul Leyland wrote:
> It's well known that factors of M(p) are of the form 2kp+1.
>
> When applying P-1 to mersenne numbers, an additional 2*p ought to be
> included in the product, over and above all the powers of prime < B1. Can
> anyone who knows for certain reassure me that this has been do
Henrik Olsen wrote:
> Using the HLT instruction to stop the processor when idle isn't something
> done by a program, but is instead a feature of the operating system.
> Windows NT and Linux does this, I think Win95 does as well, Windows 3 and
> DOS do not.
Win95 doesn't, theres a program "CPUIdl
"Brian J. Beesley" wrote:
> On 25 May 00, at 23:39, Ken Kriesel wrote:
>
> > I saw something similar once, out of hundreds of ECM curves
> > that I've run.
> > It happened on the curve being run while I adjusted memory limits
> > on the program (Version 20.4.1, April 25 file date), if I recall co
Eric Hahn wrote:
> Greetings all,
>
> I was wondering if it was common practice (ie: the norm) for
> P-1 to take the product of two or more factors when giving out
> a found factor, if two of more factors are found?
>
Yup, each factor f, for which b^E == 1 (mod f) (b is the base, usually
3, E
Stefan Struiker wrote:
> Reto:
>
> First question: goto
>
> http://www.informatik.tu-muenchen.de/~kruppa/f98/
>
> for factor98.exe download and info.
Uh oh, a link to an almost forgotten web page of mine! The Fact98.exe file is
fine (now, I had to make it chmod a+r again), but the checkpoint fi
[EMAIL PROTECTED] wrote:
> Thought: If a website uses images, does it necessarily have to care that
> text-based browsers won't see them? No.
Yes. There are *many* blind people who rely on speech output of on-screen text.
A friend of mine gradually loses eyesight and is beginning to train for
Andy wrote:
> I'm trying to compile the source code for Prime95 for a wintel machine and
> am slightly lost for how to do so. I have Visual C++, gcc, a86 and just
> about everything else.
The Linux version should compile without too much hassle, but you have to
remove the calls to the SEC5 funct
Spike Jones wrote:
> A few weeks ago, I thought someone posted something like:
>
> 2^n-1 where n is prime cannot have any factor smaller than n.
>
> Did I get that right? Is there a simple proof? spike
Factors of a mersenne number Mp are always of the form f=2*p*k+1, k may be
as small as 1.
Th
Matt Gauthier wrote:
> In message <[EMAIL PROTECTED]>, Mersenne Digest writes:
> >Do not "make clean" in linux/, this will remove all the FFT object files! Only
>
> The latest version of gas can, apparantly, handle intel syntax with
> the appropriate psuedo-op. I haven't looked into it, but it sh
I've read on the list some time ago that ECM takes, like Pollard-Rho or
P-1, O(sqrt(f)) operations mod N to find a factor f. But looking at the
factors found so far I find that hard to believe; according to that
formula, finding a 50-digit factor should be 10^15 times harder than
finding a 20-dig
"Brian J. Beesley" wrote:
>
> The question arises as to whether or not it is economical to continue
> beyond B1=4400, B2=429000. This may be a function of the
> native integer size - 64-bit systems shouldn't have any problems
> (given a suitable implementation)
I have a hacked version of
"Brian J. Beesley" wrote:
>
> Some people have indicated they'd like a version of the program with
> a pretty screen-saver interface. Fair enough, provided we can keep
> the "classic" version without the extra overhead.
>
The screen-saver idea is important for another reason.
I asked several co
"Brian J. Beesley" wrote:
>
> On 4 Feb 2001, at 0:27, Alexander Kruppa wrote:
>
> Well, you could bump NTprime's priority to 4; that would let NTprime
> steal CPU cycles off the screensaver, without being too obvious to
> the user :) Don't go any higher, a
"Brian J. Beesley" wrote:
> (1) Removing these assignments from PrimeNet and managing them
> seperately. Anyone who is prepared to make special arrangements to
> acquire these assignments is unlikely to default by reason of lack of
> commitment.
Someone is (or was?) doing something similar - Dav
Compiling a forge version with malicious code of Prime95/mprime and
distributing it is maybe the simples and possibly most devastating
attack. Since the complete source (save for the Primenet checksums but
these could either be reverse-engineered or the fake client could simply
connect to a fake
rmat number whose
primality
status was unknown. That distinction now goes to F_33; a detailed list
of known factors and primality status of Fermat numbers can be found at
http://www.prothsearch.net/fermat.
The factor was found by Alexander Kruppa on one of five AMD Thunderbird
1GHz computers loc
Hello,
I have a question whether it is possible to uss the CRT to multiply
modulo a prime d.
\phi(d) = d-1, choose k so that there are primes p_1 .. p_n where (p_1
-1)*..*(p_n-1) = k*(d-1).
Now the system of congruences (mod p_i), i=1..n, will have a cardinality
that is a multiple of phi(d). Is t
Eric Hahn wrote:
>
> If a person runs an ECM test using a B1 of 250,000 with 700
> curves (for up to 30 digits), will they also find any factors
> that they would have found if they had used a B1 of 50,000 with
> 300 curves (for up to 25 digits) ?!?
>
> Eric
If the sigma is the same, then a c
John R Pierce wrote:
> The newest Geforce3 chip also has both Pixel Shaders and Vertex Shaders
> which are each a SIMD programmable vector processors. The Pixel Shaders
> operate on every pixel and generate the actual RGB pixels while the Vertex
> Processors operate on the geometry and texture m
Steve Phipps wrote:
>
> While we're on the subject, can someone explain how to derive the group
> order for factors found using ECM? I've been carrying out ECM on an old PC
> for almost a year now, and I'd like to be able to derive, and factorise,
> the group orders for the factors that I've foun
Nathan Russell wrote:
>
> Is it (at least) theoretically possible that some larger factors are
> unfindable with ECM due to the limited number of sigma producable by
> George's random number generator?
>
> Nathan
I dont think this is a problem. Limits in the RNG would only mean
problems if it c
Alexander Kruppa wrote:
>
> gp_p(x) | go_p, and p+1-sqrt(p) <= go_p <= p+1+sqrt(p) . Since go_p(x)
Correction: I have taken the limits above from my memory which has once
again proved itself untrustworthy. The correct limits are
p+1-2*sqrt(p) < go_p <= p+1+2*sqrt(p) , a theor
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 of
Frank Solensky wrote:
>
> > I have what's probably a silly question.
> >
> > You wrote this:
> > > M727 - 94.3716% probability - 2 factors
> > > M727 - 52.8693% probability - 3 factors
> > > M727 - 6.0014% probability - 4+ factors
>
> I assumed it was that they aren't mutually exclusive -- "
> Another other way to "fix" the problem is to have the compute-
> intensive process voluntarily relinquish its timeslice at intervals
> which are much shorter than the minimum timeslice (which is
> typically of the order of 200 ms). This reduces the efficiency of the
> compute-intensive task to
Warut Roonguthai wrote:
>
> http://www.academicpress.com/inscight/11302001/grapha.htm
>
Look like the cat is out of the bag now - it's 2^13,466,917 - 1. Was
this early publication indended? I thought the press release was due
only after the independent double check completed, but then they quot
[EMAIL PROTECTED] wrote:
>
> On 4 Dec 2001, at 17:59, George Woltman wrote:
>
> > >Case 1: I finish first, find a prime and announce my discovery. I did
> > >the work but the exponent is assigned to you! Who gets the
> > >credit???
> >
> > You, get the credit. User b will be mighty disheartened
There is an _excellent_ article on the Heise Newsticker (in german).
This is one of the few I've seen that has all the facts right and it
gives a little extra info, too (i.e. it mentions Crandall's new book,
Prime Numbers, as a source for info on the DWT). Worthwhile to check out
if you read germ
Daran wrote:
>
> The math page http://www.mersenne.org/math.htm explains how to do a stage 1
> P-1 test with given bound B1, but it omits the explanation of the
> enhansement that uses B2 in stage 2. Anyone care to explain
> how this is done?
>
> Cheers
>
> Daran G.
P-1 stage 1 computes x = a
[EMAIL PROTECTED] wrote:
>
> Dear All:
>
> There were several toasts, including two synchrony
> with a couple of groups of GIMPSers in Germany who
> stayed up late to mark the occasion with us, lots of
> good food and drink, and of course conversation about
> primes (mostly shouted, as Tied Hous
Daran wrote:
>
> - Original Message -
> From: "Alexander Kruppa" <[EMAIL PROTECTED]>
> To: "Daran" <[EMAIL PROTECTED]>; <[EMAIL PROTECTED]>
> Sent: Monday, December 10, 2001 12:16 AM
> Subject: Re: Mersenne: P-1 Stage 2
>
>
> However, there's another generalisation that occurs to me that would be
> quite cheap to implement. The purpose of stage two is to catch those
> factors which are 'just out of reach' of stage 1. However another way a
> factor could be 'just out of reach' would be if the power of exactly one o
Mary Conner wrote:
> This exponent is not an isolated example. I have a printout of the first
> page of the Assigned Exponents report from Dec 7th. I compared it with
> the Assigned Exponents report from a few minutes ago, and three exponents
> off that first page have moved from their old acco
Torben Schlüntz wrote:
>
> I'd also like to know about any number fully factorized, whatever size
> it might be, and whatever size the factor(s) might be.
Try Will Edgingtons's page,
http://www.garlic.com/~wedgingt/mersenne.html .
Use used to keep a comprehensive archive of known Mersenne factor
Paul Leyland wrote:
>
> > From: Alexander Kruppa [mailto:[EMAIL PROTECTED]]
> Another issue which used to generate multiple factors by trial division in prime95
>(I don't know if it still does) is the following.
>
> All factors of Mersenne numbers fall into a
[EMAIL PROTECTED] wrote:
>
> On 26 Jan 2002, at 14:45, John R Pierce wrote:
>
> In any case it is rather doubtful that the compiler could make much
> difference to Prime95. The pieces coded in C are of the "run once"
> variety rather than being executed in every iteration.
That is true for LL t
Steve Harris wrote:
>
>
> There is already a feature which does effectively the same thing. Set
> 'InterimFiles=100' in prime.ini and it will write a save file in the
> working directory with a sequential extension every million iterations (or
> however often you set it). You must manually e
That paper sounds like a genuine revolution.
I have looked at two papers of Bernstein before, "Prime Sieves Using
Binary Quadratic Forms" together with A.O.L. Atkin (algorithm a.k.a.
"Sieve of Atkin", implementation by Bernstein available under the name
"primegen"), and "How to Find Small Factor
[EMAIL PROTECTED] wrote:
>
> On 26 Feb 2002, at 19:46, Henk Stokhorst wrote:
>
> > http://slashdot.org
> >
> > factoring breakthrough?
> >
> Doesn't look like a breakthrough, although there may be a very
> significant reduction in the amount of work required to factor
> "awkward" numbers.
>
> T
Bruce Leenstra wrote:
>
> As luck would have it, this is nearly what I am doing right now:
>
> tempvalue = (q+1)/2
> count = 1
> while tempvalue != 1 {
>if tempvalue is odd tempvalue += q
>shiftright tempvalue
>count++
> }
> v = count
I'm not sure I understand that code yet, but
Will Edgington wrote:
>
>Is it worthwhile mounting a formal attack on the Mersenne numbers
>between 20 million & say 40 million using this technique? We're
>getting quite close to this & I think Chris would not have bothered
>with these, since they were so far ahead of LL testing
There was an article on Slashdot (http://slashdot.org) recently about a
paper by Daniel Bernstein which stirred people in the cryptograpy
business by claiming that with custom designed hardware, numbers three
times as large as are feasible today could be factored.
There is a new article on Slashd
[EMAIL PROTECTED] wrote:
>
> >*** Intrinsity Arrays 2GHz Adaptive Matrix ***
>
> (rest snipped)
>
> Man, who comes up with these stupid soundalike Silicon Valley
> Tech Company names? Is this some popular Java Applet CEOs
> are using, which combines various techy-sounding word fragments to
>
Brian J. Beesley wrote:
> Hi,
>
> I was thinking about how we could improve the productivity of the project by
> reducing the proportion of candidates requiring LL testing, and had the
> following idea.
>
> P-1 factoring is useful when applied to Mersenne numbers because M(p)-1 is
> easily fa
Steinar H. Gunderson wrote:
> On Thu, Aug 01, 2002 at 07:01:04AM -0700, Gary Edstrom wrote:
>
>>I seem to remember reading that there are probabilistic tests that can
>>be run on a number. The test is repeated for a number of iterations.
>>If the test fails any iteration, then it is definitely N
Gareth Randall wrote:
> A short time ago there was a discussion relating to the prime95 process
> running as System on NT/2000, and the subject of security issues
> relating to it being accessible from a normal user's desktop came up.
> The article linked below describes a serious security issu
Daran wrote:
> I recently kluged together a script to analyse the factors in my results.txt
> file for smoothness, and discovered the following results, among others.
>
> P-1 found a factor in stage #2, B1=45000, B2=675000.
> UID: daran/1, M7893989 has a factor: 34859249922062613959
> =2*167*9533
Brian J. Beesley wrote:
After receiving this message, I removed _all_ the known factors for P721.
This was interesting, and indicates a bug, though it appears to be not very
important:
with same sigma & minimum B1 & B2 noted above, the composite factor 129
(= 3 * 43) was found. I would have e
George Woltman wrote:
At 10:31 PM 12/3/2002 +, Daran wrote:
The analysis is more complex than this. It really depends on the prime
[...]
I'd be greatly interested in such a study.
Peter Montgomery's dissertation, "An FFT Extension to the Elliptic Curve
Method of Factorization",
ftp://
Daran wrote:
>>Peter Montgomery's dissertation, "An FFT Extension to the Elliptic Curve
>>Method of Factorization",
>>ftp://ftp.cwi.nl/pub/pmontgom/ucladissertation.psl.gz ,
>
>
> What do I need to read a psl file?
Ad far as I can see it is a regular PostScript. I don't know if the
extra "l
George Woltman wrote:
Frank Hornung found the largest factor ever found using P-1.
M17504141 is divisible by the 45-digit factor
426315489966437174530195419710289226952407399
Paul Zimmermann maintains a list of P-1 records here:
http://www.loria.fr/~zimmerma/records/Pminus1.html
My, that's a beau
Phil Moore wrote:
That record didn't last long - only 11 days! Congratulations to Alex
Kruppa for his new 47 digit factor found of the 1835th Fibonacci number
by P-1 with GMP-ECM. Details at:
http://www.loria.fr/~zimmerma/records/Pminus1.html
It says that the B1 and B2 limits listed there are not
Bjoern Hoffmann wrote:
Hi,
I wondered if someone already have checked if the last mersenne
numbers +2 are double primes?
like 3+5, 5+7, 9+11, 11+13 or
824 633 702 441
and
824 633 702 443
regards
Bjoern
Mp + 2 is divisible by 3 for odd p and thus cannot be prime.
Mp - 2 however can, in theory, be
Brian J. Beesley wrote:
Hi,
(1) Could someone with the required background please tidy up my logic and
prove that the assertion above is true i.e. there is no prime 2^p-1 with p >
3 such that there are solutions to x^2 mod 2^p-1 = 2^((p+1)/2) + 2
I believe the idea is correct, but it doesn't
Alexander Kruppa wrote:
Brian J. Beesley wrote:
Hi,
(1) Could someone with the required background please tidy up my logic
and prove that the assertion above is true i.e. there is no prime
2^p-1 with p > 3 such that there are solutions to x^2 mod 2^p-1 =
2^((p+1)/2) + 2
I believe the i
75 matches
Mail list logo
