mersenneforum.org > Math complexity of Pepin's test
 Register FAQ Search Today's Posts Mark Forums Read

 2005-11-28, 22:57 #1 ixfd64 Bemusing Prompter     "Danny" Dec 2002 California 248810 Posts complexity of Pepin's test Pepin's test is used to test Fermat numbers for primality, but the numbers quickly grow too large to be tested in a reasonable amount of time. So I'm just curious, how much resources (time, memory, etc) would it take a computer of, say 3 GHz, to test a number like F33?
2005-11-29, 12:19   #2
xilman
Bamboozled!

"๐บ๐๐ท๐ท๐ญ"
May 2003
Down not across

26·181 Posts

Quote:
 Originally Posted by ixfd64 Pepin's test is used to test Fermat numbers for primality, but the numbers quickly grow too large to be tested in a reasonable amount of time. So I'm just curious, how much resources (time, memory, etc) would it take a computer of, say 3 GHz, to test a number like F33?
How long does it take for such a machine to square an integer of 2^33 bits, given that it can (for sake of argument, the precise number will be different) square a 2^6 bit integer in 1 microsecond?

Given the answer to that question, how many microseconds does it take to perform 2^33 such squarings?

Finally, there are close to 2^25 seconds per annum and 2^20 microseconds per second, so there are about 2^45 microseconds per annum. Convert your answer to the second question from microseconds to years.

No, I am not going to give you the answers to the above questions. Working them out for yourself is educational.

Paul

2005-11-29, 13:17   #3
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

11101010010002 Posts

Quote:
 Originally Posted by xilman How long does it take for such a machine to square an integer of 2^33 bits, given that it can (for sake of argument, the precise number will be different) square a 2^6 bit integer in 1 microsecond? Given the answer to that question, how many microseconds does it take to perform 2^33 such squarings? Finally, there are close to 2^25 seconds per annum and 2^20 microseconds per second, so there are about 2^45 microseconds per annum. Convert your answer to the second question from microseconds to years. No, I am not going to give you the answers to the above questions. Working them out for yourself is educational. Paul

I think your response is a bit unfair. We can not expect others to know
how to do simple arithmetic.

2005-11-29, 13:31   #4
jasonp
Tribal Bullet

Oct 2004

1101110111102 Posts

Quote:
 Originally Posted by ixfd64 Pepin's test is used to test Fermat numbers for primality, but the numbers quickly grow too large to be tested in a reasonable amount of time. So I'm just curious, how much resources (time, memory, etc) would it take a computer of, say 3 GHz, to test a number like F33?
Nobody has software that can handle a number that big. Note that even if you did, you'd need at least 4GB of memory just to fit intermediate results. See the F24 paper of Crandall, Mayer and Papadopoulos for some estimates.

jasonp

2005-11-29, 14:44   #5
Mystwalker

Jul 2004
Potsdam, Germany

3×277 Posts

Quote:
 Originally Posted by jasonp See the F24 paper of Crandall, Mayer and Papadopoulos for some estimates.
I'm always amused about the form of self-citations in scientific papers.
Similar to the use of "we"/"the authors", when there is only one...

 2005-11-29, 16:01 #6 akruppa     "Nancy" Aug 2002 Alexandria 1001101000112 Posts I often wondered about the "we" form of scientific papers until I happened to read one where the author kept using "I". It was very hard to read. I think someone speaking to you as a person in the "I" form distracts too much from the subject matter - due to the author appearing as an actual person in the text, the brain thinks there's a dialogue and kinda switches into social interaction mode which makes you lose focus on the hard facts. My .02โฌ, Alex
 2005-11-29, 22:18 #7 ewmayer ∂2ω=0     Sep 2002 Repรบblica de California 2·32·653 Posts I like the "we" because it always struck me as giving the feel that the reader is being invited to participate in a collaborative learning experience. My current in-development Mlucas v3.0 has Fermat-mod capability and can handle numbers the size of F33 (a single modmul needs on the order of a minute on a fast single-CPU machine), but as has been stated, even if you had a massively parallel machine and a perfectly parallelized FFT, the sheer number of modmuls needed for the Pe'pin test of F33 is overwhelming - you would need to be able to do a mod-F33 squaring every few milliseconds to be able to test F33 in under a year. With a perfectly parallelized FFT (and no such beast exists - it's extremely tough to get decent parallel big-FFT performance with as few as 4 CPUs) you would need several tens of thousands of CPUs to achieve that kind of performance. That kind of hardware is not out of reach (assuming you can get one or more of the world's economic superpowers to give up their global-climate or nuclear-weapons simulations for, oh, just the coming year - y'all weren't really going to *use* that billion-dollar supercomputer for anything, were you?), but as I said there is no software that can wring anywhere close to the needed big-FFT parallelism out of it. Ask me again in ten years, or whenever the needed number of CPUs has dropped to around 1000 or less, and maybe then things will look less daunting.
2005-11-30, 13:48   #8
fatphil

May 2003

3×5×17 Posts

Quote:
 Originally Posted by akruppa I often wondered about the "we" form of scientific papers until I happened to read one where the author kept using "I". It was very hard to read. I think someone speaking to you as a person in the "I" form distracts too much from the subject matter - due to the author appearing as an actual person in the text, the brain thinks there's a dialogue and kinda switches into social interaction mode which makes you lose focus on the hard facts.
DJB, in one of his papers asterisks the first "I", and has a footnote at the bottom saying something along the lines of 'I refuse to continue mechanically replacing "I" by "we"'. I forget which one though, I can hunt it out if anyone's interested.

I have to differ when it comes to preferences. If I know a paper has only a single author, every time I see "we" I get this "what? are you a nutcase, or royalty?" distraction which might make me lose focus on the hard facts.

As long as the maths is clear (and the steps are gentle) I don't really care about either pronouns, or active/passive, or anything.

2005-11-30, 19:06   #9
akruppa

"Nancy"
Aug 2002
Alexandria

46438 Posts

Quote:
 Originally Posted by fatphil DJB, in one of his papers asterisks the first "I", and has a footnote at the bottom saying something along the lines of 'I refuse to continue mechanically replacing "I" by "we"'. I forget which one though, I can hunt it out if anyone's interested.
I remember that comment - I think we're talking about the same paper. On further thought, I don't think it could have been anyone but Dan.

Alex

Last fiddled with by akruppa on 2005-11-30 at 20:42

 2005-11-30, 19:10 #10 Zeta-Flux     May 2003 7·13·17 Posts I like the advice given to me by George Bergman (a professor at UC Berkeley). He prefers to use "we" when he is involving the reader in something. (Like, "We now divide n by 3.") He uses "I" when he is referring only to himself. (Like, "I conjecture that there are no counter-examples...") Makes sense.
2005-11-30, 19:46   #11
philmoore

"Phil"
Sep 2002
Tracktown, U.S.A.

25×5×7 Posts

Quote:
 Originally Posted by ixfd64 Pepin's test is used to test Fermat numbers for primality, but the numbers quickly grow too large to be tested in a reasonable amount of time. So I'm just curious, how much resources (time, memory, etc) would it take a computer of, say 3 GHz, to test a number like F33?
The benchmarks page: http://www.mersenne.org/bench.htm says that it would take a 3800 MHz Pentium-4
about 4050 years to do a LL test on a number of that size, and a Pepin test on F33 should be comparable.
But a 4GB FFT size would create some problems. Interestingly enough, F31, which was considered out of reach before Alex Kruppa found a factor, would take on the order of 250 years according to
the benchmarks page, which a multi-processor system could conceivably bring down to a few decades.

Last fiddled with by philmoore on 2005-11-30 at 23:06 Reason: added spoiler tags

 Similar Threads Thread Thread Starter Forum Replies Last Post R. Gerbicz Number Theory Discussion Group 15 2018-09-01 13:23 carpetpool Miscellaneous Math 4 2017-02-09 19:26 T.Rex Math 12 2016-04-03 22:27 kurtulmehtap Math 10 2013-03-20 14:15 T.Rex Math 9 2007-05-29 21:15

All times are UTC. The time now is 17:12.

Tue Dec 6 17:12:43 UTC 2022 up 110 days, 14:41, 0 users, load averages: 1.35, 2.03, 1.75