20140529, 11:36  #1 
May 2014
2_{16} Posts 
Mersenne "like" processing
Sorry for the lack of background knowledge... I have few questions that I would really appreciate some help.
A  Is a prime in the form 2^nc  c > 1 and 1 = c mod 2 verifiable through same methods that Mersenne numbers are? B  Can I speed up PRP verification of the formula above with programs like Cudalucas for L.Lemer Tests or Equivalent? (maybe not Cudalucas one time that I can't define constants c != 1) C  Are PRP tests processing time in general linear to bitlength? I got average time oscilating from 500ms to 300ms per bit (LLR) but if this really goes linear, i won't be able to finish the job before several months. 
20140529, 14:00  #2 
May 2014
2 Posts 
On "Can I speed up PRP verification" and "Are PRP tests processing time" I meant to say Probable Prime.

20140529, 14:48  #3  
Account Deleted
"Tim Sorbera"
Aug 2006
San Antonio, TX USA
1000010110110_{2} Posts 
Quote:
Quote:
It is similar to Mersenne numbers: if you double the n, you roughly double the time per iteration and the number of iterations, so it's proportional to bitlength^2 (quadratic), not bitlength^1 (linear). The time per iterations is constant for the duration of your test. E.g. if you need to do 30 million iterations, it will take around (30 million * 300 ms =) 15 weeks. Last fiddled with by MiniGeek on 20140529 at 14:51 

20140530, 11:48  #4  
"Bob Silverman"
Nov 2003
North of Boston
2^{2}·1,871 Posts 
Quote:
and some specific numbers. To achieve roughly linear time per iteration, the modular multiplications must be done by convolution methods that automatically do the modular reduction (such as DWT), or which allow the reduction to be done in linear time. (which is true for 2^n +/ c for small c). Generic PRP tests run in time O(log^3 N) where N is the number being tested 

20140530, 21:52  #5  
∂^{2}ω=0
Sep 2002
República de California
3^{4}·5·29 Posts 
Quote:


20140602, 11:19  #6  
"Bob Silverman"
Nov 2003
North of Boston
2^{2}·1,871 Posts 
Quote:
wrote "Parallel Polynomial Arithmetic over Finite Rings" back in the 90's. Aho, Hopcroft & Ullman's book on Algorithms gives a terrific exposition. [A terrific book in general; I learned a lot from it] However, it is horribly slow when compared to multiplication. AT least my implementation was. [perhaps a lousy implementation??] 

20140607, 14:29  #7 
Tribal Bullet
Oct 2004
6735_{8} Posts 
For Nbit operands, Nbit general modular multiplication needs about three N*N>2Nbit multiplies if a generalized reciprocal is already computed; see the functions ap_recip and ap_mul at the bottom of here. This was used with FHT multiplies in Msieve's NFS square root until I switched to using GMP.

20140607, 23:18  #8  
"Bob Silverman"
Nov 2003
North of Boston
1D3C_{16} Posts 
Quote:
Computing N mod p_i for i=0,1,2,...... requires computing a new inverse each and every time. 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
gpuOwL: an OpenCL program for Mersenne primality testing  preda  GpuOwl  2793  20221007 05:01 
AouessareEl HaddouchiEssaaidi "test": "if Mp has no factor, it is prime!"  wildrabbitt  Miscellaneous Math  11  20150306 08:17 
"On factors of Mersenne numbers"  Seiji Tomita  cheesehead  Math  6  20091215 17:45 
Would Minimizing "iterations between results file" may reveal "is not prime" earlier?  nitai1999  Software  7  20040826 18:12 
trial factoring of "small" mersenne numbers  antiroach  Lone Mersenne Hunters  6  20030716 23:35 