mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2005-11-28, 22:57   #1
ixfd64
Bemusing Prompter
 
ixfd64's Avatar
 
"Danny"
Dec 2002
California

32·269 Posts
Default 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?
ixfd64 is offline   Reply With Quote
Old 2005-11-29, 12:19   #2
xilman
Bamboozled!
 
xilman's Avatar
 
"𒉺𒌌𒇷𒆷𒀭"
May 2003
Down not across

73·151 Posts
Default

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
xilman is offline   Reply With Quote
Old 2005-11-29, 13:17   #3
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

1D2416 Posts
Default

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.
R.D. Silverman is offline   Reply With Quote
Old 2005-11-29, 13:31   #4
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

354310 Posts
Default

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
jasonp is offline   Reply With Quote
Old 2005-11-29, 14:44   #5
Mystwalker
 
Mystwalker's Avatar
 
Jul 2004
Potsdam, Germany

83110 Posts
Wink

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...
Mystwalker is offline   Reply With Quote
Old 2005-11-29, 16:01   #6
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

246710 Posts
Default

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
akruppa is offline   Reply With Quote
Old 2005-11-29, 22:18   #7
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
República de California

32×1,297 Posts
Default

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.
ewmayer is offline   Reply With Quote
Old 2005-11-30, 13:48   #8
fatphil
 
fatphil's Avatar
 
May 2003

3×7×11 Posts
Default

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.
fatphil is offline   Reply With Quote
Old 2005-11-30, 19:06   #9
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

2,467 Posts
Default

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
akruppa is offline   Reply With Quote
Old 2005-11-30, 19:10   #10
Zeta-Flux
 
Zeta-Flux's Avatar
 
May 2003

60B16 Posts
Default

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.
Zeta-Flux is offline   Reply With Quote
Old 2005-11-30, 19:46   #11
philmoore
 
philmoore's Avatar
 
"Phil"
Sep 2002
Tracktown, U.S.A.

3·373 Posts
Default

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
philmoore is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Fast and robust error checking on Proth/Pepin tests R. Gerbicz Number Theory Discussion Group 15 2018-09-01 13:23
Complexity of Chinese Remainder Theorem carpetpool Miscellaneous Math 4 2017-02-09 19:26
Use Pepin's Tests for proving primality of Mersenne numbers ? T.Rex Math 12 2016-04-03 22:27
Complexity analysis of 3 tests kurtulmehtap Math 10 2013-03-20 14:15
Complexity of LLT T.Rex Math 9 2007-05-29 21:15

All times are UTC. The time now is 20:13.


Sun Nov 28 20:13:35 UTC 2021 up 128 days, 14:42, 0 users, load averages: 1.13, 1.22, 1.18

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.