Wheel factorization: Efficient?

[CRGreathouse]

What is this supposed to return?

[3.14159]

What is this supposed to return?

If prime, the number itself. If it fails trial division, the smallest prime factor.

[CRGreathouse]

Originally Posted by 3.14159

If prime, the number itself. If it fails trial division, the smallest prime factor.

Then you need to change the last line of the program (other than the "};" of course). And what's it supposed to return if the number is composite without a known factor?

[3.14159]

Then you need to change the last line of the program (other than the "};" of course). And what's it supposed to return if the number is composite without a known factor?

It returns zero if it's a composite that passes. So there are no pseudoprimes.

Testing for c100: 317305983867984894552374513880330942325323897104138220309522782479794265138440652957829496038865542387
Result = 31 ms.

c200: 47 ms.
c400: 78 ms.
c800: 218 ms.
c1600: 702 ms.

p200: 47 ms.
p400: 94 ms.
p800: 219 ms.

[CRGreathouse]

Originally Posted by 3.14159

It returns zero if it's a composite that passes. So there are no pseudoprimes.

I'm not sure what that has to do with what I said. You wrote of the program:

Originally Posted by 3.14159

If prime, the number itself. If it fails trial division, the smallest prime factor.

But for 101 it returns 1, not 101.

[3.14159]

But for 101 it returns 1, not 101.

Ah. I figured that one out. It only returns the number itself whenever you specify a base. Pretty much, the prime test can handle anything that's ≤ 1k digits in a few seconds. For larger primes, Proth will do to generate such numbers.

≈ 2000 digits: Approximately 1 second.
≈ 1000 digits: About 0.28 seconds.
≈ 3000 digits: About 2.65 seconds.

Testing the second largest prime I have ever found: 94.25 seconds.

Great. It's suitable for small primes and mid-sized primes.

Also: It may return either: Mod(1, n), or Mod(n-1, n) for primes.

Params set: SPRP = Trial division + Miller-Rabin test (Primality confirmation: Perform here. Be warned: 900+ digits, it uses Miller-Rabin as a test, use this only for small integers. For larger cases, use PARI's isprime(n) function.)

WPRP = Fermat's primality test"

Hey: I thought of something:
I'm going to code the original 7-step test, and see by how much it is slower, in the long run. Tips?

Here's my long-winded guess:

primetest(n) = {
if(ispower(n) == 1,print(1));
forprime(p=2,nextprime(500),
if(n%p==0,return(p))
);
if(Mod(b, n)^(n-1) == 1,print(n));
my(s=valuation(n-1,2),d=n>>s);
n = Mod(b, n)^d;
if (n == 1, return(1));
while(s--,
if (n == -1, return(1));
n = n^2;
);
n == -1
};

[science_man_88]

Originally Posted by 3.14159

Ah. I figured that one out. It only returns the number itself whenever you specify a base. Pretty much, the prime test can handle anything that's ≤ 1k digits in a few seconds. For larger primes, Proth will do to generate such numbers.

≈ 2000 digits: Approximately 1 second.
≈ 1000 digits: About 0.28 seconds.
≈ 3000 digits: About 2.65 seconds.

Testing the second largest prime I have ever found: 94.25 seconds.

Great. It's suitable for small primes and mid-sized primes.

Also: It may return either: Mod(1, n), or Mod(n-1, n) for primes.

Params set: SPRP = Trial division + Miller-Rabin test (Primality confirmation: Perform here. Be warned: 900+ digits, it uses Miller-Rabin as a test, use this only for small integers. For larger cases, use PARI's isprime(n) function.)

WPRP = Fermat's primality test"

Hey: I thought of something:
I'm going to code the original 7-step test, and see by how much it is slower, in the long run. Tips?

Here's my long-winded guess:

primetest(n) = {
if(ispower(n) == 1,print(1));
forprime(p=2,nextprime(500),
if(n%p==0,return(p))
);
if(Mod(b, n)^(n-1) == 1,print(n));
my(s=valuation(n-1,2),d=n>>s);
n = Mod(b, n)^d;
if (n == 1, return(1));
while(s--,
if (n == -1, return(1));
n = n^2;
);
n == -1
};

I may no nothing about the test but I'm pretty sure you don't have to have the ==1 part for ispower as it should just check it itself.

[3.14159]

Testing.. Dammit. I have a syntax error. The error reads:

 *** Mod: incorrect type in Rg_to_Fl.

[science_man_88]

Originally Posted by 3.14159

Testing.. Dammit. I have a syntax error. The error reads:

 *** Mod: incorrect type in Rg_to_Fl.

you also have what I pointed out with something extra than what's needed. I can't spot much else but I'm not good with PARI(especially the new stuff).

[CRGreathouse]

Originally Posted by 3.14159

Hey: I thought of something:
I'm going to code the original 7-step test, and see by how much it is slower, in the long run. Tips?

1. Don't print 1 when a power is found, instead return 0.
2. You can't raise b to a power mod n unless you know what b is. (I suggest adding an optional argument for b.)
3. Don't print n when Mod(b, n)^(n-1) == 1, instead return n.
4. Change the line n == -1 to an if statement returning either 0 or n.

I see four steps, not seven (power, trial division, Fermat test, M-R test). Also I suggest adding an addhelp explaining how the function works: you wouldn't want someone doing

if(primetest(n), print(n" is prime"))

the way you've written it.

[3.14159]

.. I can't code it altogether. It has to be done in separate tests for the original.