Wheel factorization: Efficient?

[3.14159]

My point: You spend vastly more time weeding them out then if you simply let the M-R tests catch them, because your tests happen on non-powers as well. The wasted time is many orders of magnitude larger than the time saved (see my post for specific numbers) at any reasonable size.

Using the check, all the tests would be on integers that are NOT nth powers. (Which would be nearly every integer, as the density of nth powers approaches zero.)

But, admittedly, my reasoning was flawed.

All that remains is:
1. Choose random integer
2. Trial division up to 10^6 (Reduced to 10^6)
3. Miller-Rabin test
4. Primality confirmation.

Optional: Perform an nth power check.

But: How efficient would the trial division be?
1/2 of all integers are divisible by 2. All even numbers are eliminated immediately.
1/3 of all integers are divisible by 3. But 1/2 of those are even. So, 1/6 of the integers have 3 as a smallest prime factor.
1/5 of all the integers are divisible by 5. 1/2 of those are divisible by 2. 1/10 of integers are odd numbers divisible by 5. But, 1/3 of these integers are divisible by 3.
.. The efficiency would simply be determined by (x# - (euler's totient(x#))/x#.
For 1000000#, the product of 2 * 3 *5*7*11*13*17*19*23*29*31*...*999983, euler's totient(x) would be (2-1)*(3-1)*(5-1)*(7-1)..

But.. I need a numerical result first. :| Unfortunately, PARI does not know what primorials are, yet..

I'll just write: prime(1) * prime(2) * prime(3) * ... * prime(78498). Text editors.

[retina]

Originally Posted by 3.14159

Optional: Perform an nth power check.

OptionalPointless waste of effort: Perform an nth power check.

Don't forget to adjust your TF limit based upon the number size.
Don't forget to adjust your MR test count based upon the number size.

[xilman]

Originally Posted by 3.14159

Using the check, all the tests would be on integers that are NOT nth powers. (Which would be nearly every integer, as the density of nth powers approaches zero.)

But, admittedly, my reasoning was flawed.

All that remains is:
1. Choose random integer
2. Trial division up to 10^6 (Reduced to 10^6)
3. Miller-Rabin test
4. Primality confirmation.

Optional: Perform an nth power check.

Your current recommendation appears reasonable, though I personally would specify step 3 more precisely: something like "a single MR test to a randomly chosen base".

Paul

[3.14159]

Don't forget to adjust your TF limit based upon the number size.
Don't forget to adjust your MR test count based upon the number size.

Leave the params alone, the test is good enough as is. It's time-wasting to try to adjust the params to fit your "ideal test".

Trial division's efficiency:
10k: 93%
100k: ≈ 94%
1M: ≈ 95%

1 in 20 pass. That's good enough for me.

So, Retina: Since you would like to mess with the params, what do you think they should be?

[retina]

Going through some old code I see I used this:

TF_bits = 2(log₂(log₂(number)) - 4

[3.14159]

Testing a random 150-digit number:
640552686568398413516426919223357728279912327120302109778516984973296910867431808451611740398561987580967216226094312377767778241368426651540749005659.

Trial division up to 10^6 yields divisibility by two pairs of consecutive prime numbers (3, 7) (173, 179)

[retina]

And we haven't even begun to discuss the meaning of 'random'.

Curious to know how you are generating them.

It does matter if you want to use the primes for anything to do with security/encryption.

[3.14159]

And we haven't even begun to discuss the meaning of 'random'.

Curious to know how you are generating them.

I'm generating them via PARI's "Random(n)" function. I generated 500 random integers:

Here is a snippet of some of them:

%305 = 920117259669212245395826734557263643310815776873901470609489756566897084845796605066517216547693086346111896176864586376767114722039031730901980300393
(16:08) gp > random(10^150)
%306 = 391338178282469899873179611162567028989261328981768310711499853030577807821153359543897205996134115393885587748597424511781763627551002413143153013912
(16:08) gp > random(10^150)
%307 = 483327727868817071664104952233965620086161380990460556288570534629555258159445497255073199919322097098997209361169698441379571921327033225858175900853
(16:08) gp > random(10^150)
%308 = 268364851011129165067564993577229988619163567578599552234020904668698600332366058495083299558213992347599057978089962555271109540658927560335557504322
(16:08) gp > random(10^150)
%309 = 568717512274641701468833159423971722551858917582584542804113878360026669014453608312393779733410897085286469126700177956100384726287206217147676382909
(16:08) gp > random(10^150)
%310 = 956632976012366265983287080752059887649354940676494208955295389839939170986304687366993426093835455237167715893048253597668843527000247233020891629992
(16:08) gp > random(10^150)
%311 = 754374345716061224119641827648924963879438475977574791267521229394321579947607236429812524262233450443482224961632520505241294006993745735071444956801
(16:08) gp > random(10^150)
%312 = 34216520588425857272874977376469534037304448162005202760866664780298047969230783347622336193347507469460787721506023129742082089736081781897071037898
(16:08) gp > random(10^150)
%313 = 618426543563069153144327131192988196164472168222385652345704391047310867953845453638812608225857883864213275140049502947585919829518652994711005691905
(16:08) gp > random(10^150)
%314 = 79272252747556933387359292342544680955303551924153824672470148844356957802651115371421496952414952120181173319775476406478403185767808778635822906792
(16:08) gp > random(10^150)
%315 = 739023351936784807700328358475606730262795460743054325023507354621136875629209496854357888452923025720309031273519355877168632234126232548444756244285
(16:08) gp > random(10^150)
%316 = 669931609703571529095460010329045635899832407297546011101770648256311645197175751537955975312999774895482335375479193362977569593745297624446105165122
(16:08) gp > random(10^150)
%317 = 694261868721699995048395439919787048072042737745222004253131882237566680963978666283013551001695737720587614503056582478029462252590877791826073706549
(16:08) gp > random(10^150)
%318 = 384295732721137574539730193519552498415126878323303674218321804691611685885018987860387049474206032344510425166273311934905120000687512251653227425944
(16:08) gp > random(10^150)
%319 = 62289139969645808383826626043333098045936501427308020432469026013032584322057071887724591517161027773071346537279478729891482094204293307773470097129
(16:08) gp > random(10^150)
%320 = 800512946385014606742738110482412566505332051992456346265633434690373250466444424551152833676113548257700086736405882697127945502507382294890735205290
(16:08) gp > random(10^150)
%321 = 421222272589343667953668574409962945103106720947087386405558788830009254539508856037495298263004986231020758035545020943999514083383966288147362191193
(16:08) gp > random(10^150)
%322 = 496693757205523684373175383649450425308347317885328846336840029389835066708899093537844099321433348476505389655494246025365607139651452180438359671416
(16:08) gp > random(10^150)
%323 = 349193625426232142232755788680212202208694637476299850860732655413211641421793754452308396699617862009600863753581223906588493259573921114540269596037
(16:08) gp > random(10^150)
%324 = 50978046010499802770712013203249095850194377737843881972139304999810324230563379859867603479899632150267132112859146599147416466651233250171506641154
(16:08) gp > random(10^150)
%325 = 424314983523561460555774374173667442481281393243166338082680381534532240387702228376872621556645679306896086502727477063740804491568119499691203675502
(16:08) gp > random(10^150)
%326 = 41468232597539335949533286798045730831060949382000442865744206029052242780448631196811358851428054057923923996951690774568810936816726500256884183880
(16:08) gp > random(10^150)
%327 = 224705297053306837431815170039045713463204369551757286397051706771146876279998785859084961252329854178412632119237483855159075899870973559953926398738
(16:08) gp > random(10^150)
%328 = 46308241222290412121446242742942405065125059012705064077226110814848449556718554167867387432595430277448316964340222518048432448628992234585781413194
(16:08) gp > random(10^150)
%329 = 328507568687122516335648830196358865138147780207385413117200107965755608576739209508228308481802493935066286975378161870272858383553903447646093052530
(16:08) gp > random(10^150)
%330 = 643606735179450764123823396729018916970612648409831895314817201746005641088480533380611716205026053955086867703108548790224722493367909873837269107464
(16:08) gp > random(10^150)
%331 = 313856357244468540144097737395515911357488203880237889057957261079809489063600886204895496334562944618159693508865860573756399271687548985616338059150
(16:08) gp > random(10^150)
%332 = 411514803805762310051245285199412560172071064214108156409813572068952418371849669209274074331663164571817321766036319217430252859116873866513668944002
(16:08) gp > random(10^150)
%333 = 758850960917293274752154948592179880072734168887455950591408839303942567688118721773502963609845845345329544671765199097269372963660952367784500037222
(16:08) gp > random(10^150)
%334 = 928140188764294795368612330884203916749989717970766947761773972447659974708107517398554432665641448283202737952049079450946292743152187534562761961912
(16:08) gp > random(10^150)
%335 = 241636225497605357345221802176637649197856795581341770266138823515399285049591044760425463090062633504553859156936909372979408824808524623233643520762
(16:08) gp > random(10^150)
%336 = 771605883654836567423879697797538150786388604725016487685900249049572007990239522488887552273527429454914482701058234175953244409545652603503026375338
(16:08) gp > random(10^150)
%337 = 340310527450456234336220672487597558766007144652587663917024757402636373454643226773856109511064204391020506974968475675513572590840065287701046188362
(16:08) gp > random(10^150)
%338 = 520023673615904607122977328865828844901452216194813046406745273351657344064923251261376026131593278801262507434207510379660827874648615866261050261336
(16:08) gp > random(10^150)
%339 = 633011547439126650392342675824851964671204546870125211924362266555136946849962913961093785833295701021303728533359845865967308668720443705911048777046

[CRGreathouse]

Originally Posted by 3.14159

But.. I need a numerical result first. :| Unfortunately, PARI does not know what primorials are, yet..

I'll just write: prime(1) * prime(2) * prime(3) * ... * prime(78498). Text editors.

A simple Pari primorial program is

primorial(x)={
  my(t=1);
  forprime(p=2,x,t*=p);
  t
}

If you want it to be efficient (which doesn't usually matter), split the product into different parts so you're not accumulating large partial products. Even with the extra overhead this is much more efficient even for modest values of x. Here's the code I'm using:

primorial(n)={
	my(t1=1,t2=1,t3=1,t4=1);
	forprime(p=2,n>>3,t1=t1*p);
	forprime(p=(n>>3)+1,n>>2,t2=t2*p);
	t1=t1*t2;t2=1;
	forprime(p=(n>>2)+1,(3*n)>>3,t2=t2*p);
	forprime(p=((3*n)>>3)+1,n>>1,t3=t3*p);
	t1=t1*(t2*t3);t2=1;t3=1;
	forprime(p=(n>>1)+1,(5*n)>>3,t2=t2*p);
	forprime(p=((5*n)>>3)+1,(3*n)>>2,t3=t3*p);
	t2=t2*t3;t3=1;
	forprime(p=((3*n)>>2)+1,(7*n)>>3,t3=t3*p);
	forprime(p=((7*n)>>3)+1,n,t4=t4*p);
	t1*(t2*(t3*t4))
};
addhelp(primorial, "primorial(n): Returns the product of each prime less than or equal to n. Sloane's A034386.");

(Actually I'm using a C version of this that avoids re-looping through the prime table and avoids dynamic typing, but frankly the savings are small.)

Of course in the case of your calculation you'd be much better off just doing

t=1.;forprime(p=2,1e6,t*=1-1/p);t

[3.14159]

And we haven't even begun to discuss the meaning of 'random'.

.. Just look in a dictionary.

Random: "proceeding, made, or occurring without definite aim, reason, or pattern"

The only "pattern" is that all the integers I posted are about 150 digits in size, as 90% of the integers are 150 digits in size. 99% are either 149 or 150 digits in size. 99.9% are 148-150 digits in size. Etc, etc.

[CRGreathouse]

Originally Posted by 3.14159

I'm generating them via PARI's "Random(n)" function.

Retina: This uses Brent’s XORGEN ("a generalisation of Marsaglia's 'xorshift' random number generators") to simulate a uniform random distribution on the integers from 0 to n-1. I'm sure 3.14159 doesn't intend to use these for crypto.