20051128, 22:57  #1 
Bemusing Prompter
"Danny"
Dec 2002
California
2488_{10} 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? 
20051129, 12:19  #2  
Bamboozled!
"๐บ๐๐ท๐ท๐ญ"
May 2003
Down not across
2^{6}·181 Posts 
Quote:
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 

20051129, 13:17  #3  
"Bob Silverman"
Nov 2003
North of Boston
1110101001000_{2} Posts 
Quote:
I think your response is a bit unfair. We can not expect others to know how to do simple arithmetic. 

20051129, 13:31  #4  
Tribal Bullet
Oct 2004
110111011110_{2} Posts 
Quote:
jasonp 

20051129, 14:44  #5  
Jul 2004
Potsdam, Germany
3×277 Posts 
Quote:
Similar to the use of "we"/"the authors", when there is only one... 

20051129, 16:01  #6 
"Nancy"
Aug 2002
Alexandria
100110100011_{2} 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 
20051129, 22:18  #7 
∂^{2}ω=0
Sep 2002
Repรบblica de California
2·3^{2}·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 indevelopment Mlucas v3.0 has Fermatmod capability and can handle numbers the size of F33 (a single modmul needs on the order of a minute on a fast singleCPU 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 modF33 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 bigFFT 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 globalclimate or nuclearweapons simulations for, oh, just the coming year  y'all weren't really going to *use* that billiondollar supercomputer for anything, were you?), but as I said there is no software that can wring anywhere close to the needed bigFFT 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. 
20051130, 13:48  #8  
May 2003
3×5×17 Posts 
Quote:
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. 

20051130, 19:06  #9  
"Nancy"
Aug 2002
Alexandria
4643_{8} Posts 
Quote:
Alex Last fiddled with by akruppa on 20051130 at 20:42 

20051130, 19:10  #10 
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 counterexamples...") Makes sense.

20051130, 19:46  #11  
"Phil"
Sep 2002
Tracktown, U.S.A.
2^{5}×5×7 Posts 
Quote:
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 multiprocessor system could conceivably bring down to a few decades. Last fiddled with by philmoore on 20051130 at 23:06 Reason: added spoiler tags 

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  20180901 13:23 
Complexity of Chinese Remainder Theorem  carpetpool  Miscellaneous Math  4  20170209 19:26 
Use Pepin's Tests for proving primality of Mersenne numbers ?  T.Rex  Math  12  20160403 22:27 
Complexity analysis of 3 tests  kurtulmehtap  Math  10  20130320 14:15 
Complexity of LLT  T.Rex  Math  9  20070529 21:15 