Wheel factorization: Efficient?

[3.14159]

Ah. In that case "If b=x is present, it will perform a Miller-Rabin test using base x." is incorrect.

Is that why 1373653 returns as a prime when tested with b=2 or b=3, when the trial division settings are reduced to the point where it passes?

(15:30) gp > isSPRP(1373653, b=2)
time = 0 ms.
%290 = 1
(15:30) gp > isSPRP(1373653, b=3)
time = 0 ms.
%291 = 1

Another example:

(15:32) gp > isSPRP(390937, b=2)
time = 0 ms.
%300 = 1
(15:32) gp > isSPRP(390937, b=7)
time = 0 ms.
%301 = 0

So, why does 390937 pass for b=2 and fail for b=7? Please, enlighten me with your brilliant explanation.
Now that both of those objections are entirely debunked, continuing on with regularly scheduled programming, so to speak.

[CRGreathouse]

Originally Posted by 3.14159

So, why does 390937 pass for b=2 and fail for b=7? Please, enlighten me with your brilliant explanation.

Would you post your code?

[3.14159]

Would you post your code?

It's the code you posted earlier, except b=random(n)

isSPRP(n, b=random(n)) = {
forprime(p=2,nextprime(10^6),
if(n%p==0,return(p))
);
my(s=valuation(n-1,2),d=n>>s);
n = Mod(b, n)^d;
if (n == 1, return(n));
while(s--,
if (n == -1, return(n));
n = n^2;
);
n == -1
};

[CRGreathouse]

Originally Posted by 3.14159

It's the code you posted earlier, except b=random(n)

In the declaration? (I thought you put it in the Mod() statement, in which case it worked as I described... thus my request for code rather than description.) That's amusing... somewhat inadvisable in general, but it works in this case. Yes, in that case the only problems I have with the documentation is that it doesn't explain return values, and the only problems I have with the code are its inconsistent returns types* and the fact that it may test base 0 or 1. I'm not worried about the latter, though, as long as you use the code only for large numbers.

[3.14159]

In the declaration? (I thought you put it in the Mod() statement, in which case it worked as I described... thus my request for code rather than description.)

I would probably mess up the syntax if that were the case.

That's amusing... somewhat inadvisable in general, but it works in this case.

At least it won't give a consistent list of pseudoprimes that passes.

Yes, in that case the only problems I have with the documentation is that it doesn't explain return values, and the only problems I have with the code are its inconsistent returns types and the fact that it may test base 0 or 1.

Return values are self-explanatory anyway! And: It only takes one composite return to declare the number a proven composite. I modified the returns back to the default 1 and 0, 1 meaning prime, 0 meaning composite.

Also: A lucky find without any modifications: Largest keyjabbed prime I've found: 7242389437701561147346511132232465821 (Passed b= 2, and 5 randoms.)
+5 for a keyjabbed prime, +5 for a prime number of digits (37)

[CRGreathouse]

Originally Posted by 3.14159

Return values are self-explanatory anyway!

It's not self-explanatory to me! The script returns the smallest prime factor of n, if n has a prime factor below 1000033; Mod(1, 1), if n is 1; an error, if n is less than 1; 1, Mod(1, n), or Mod(n-1, n) if none of the preceding apply but n is a base-b probable-prime; 0, if n is a proven composite without known factors.

Originally Posted by 3.14159

I modified the returns back to the default 1 and 0, 1 meaning prime, 0 meaning composite.

Ah, much better. Now you can use it in an if statement without trouble.

Originally Posted by 3.14159

Also: A lucky find without any modifications: Largest keyjabbed prime I've found: 7242389437701561147346511132232465821 (Passed b= 2, 3, 5, 7, 11, 13, 17)

Nice. You can certify primality, if you like, with isprime(N, 1).

[3.14159]

It's not self-explanatory to me! The script returns the smallest prime factor of n, if n has a prime factor below 1000033; Mod(1, 1), if n is 1; an error, if n is less than 1; 1, Mod(1, n), or Mod(n-1, n) if none of the preceding apply but n is a base-b probable-prime; 0, if n is a proven composite without known factors.

See above for clarification. Also: 1000003, which means it any composite number up to nextprime(1000003)^2 will fail TD. And, now that the return values are at default settings: It's self-explanatory.

Ah, much better. Now you can use it in an if statement without trouble.

Excellent.

Nice. You can certify primality, if you like, with isprime(N, 1).

I certified it using APRT-CL on Alpertron's app. Also:.. A curious question: What test does isprime use? (When there is no flag indicating the use of Pocklington or APR-CL)

[CRGreathouse]

If the number is small enough to fit into one machine word, it does a special test. If not:

1. Trial divide to 101 (efficiently, not one-at-a-time)
2. Performs a BPSW test (base-2 strong test followed by a Lucas test)
3. If n is less than 10^15, return true (actually, 10^16 would work)
4. Attempt to factor n-1
5. If sufficiently smooth, do a Selfridge n-1 test
6. If almost smooth enough, augment a Selfridge n-1 test with the Brillhart-Lehmer-Selfridge test
7. Otherwise, fall back to APRCL.

[3.14159]

Extended my prime search for Proth-GFNs to 150000 for k's range. Also, increased sieving by a factor of 4. This left 1/14 of the candidates.

A curious question: For WinPFGW, there's a bunch of settings like that of its predecessor, PrimeForm. However, they are inaccessible. Why add options such as this, knowing that they are useless because they cannot be accessed?

[science_man_88]

Originally Posted by 3.14159

I certified it using APRT-CL on Alpertron's app. Also:.. A curious question: What test does isprime use? (When there is no flag indicating the use of Pocklington or APR-CL)

straight from the program help:

isprime(x,{flag=0}): true(1) if x is a (proven) prime number, false(0) if not. If flag is 0 or omitted, use a combination of algorithms. If flag is 1, the
primality is certified by the Pocklington-Lehmer Test. If flag is 2, the primality is certified using the APRCL test.

[3.14159]

Update: Prime found! 10462 * 1296⁸¹⁹² + 1 is a probable prime! (Proth-GFN.) (Validating w/SPRP for random base. Might take 5-10 mins. Used base 2 to speed it up.)
This is simply excellent. A PRP25503.

Also: Passed base 2 SPRP test as well. (How seriously should one take PFGW's PRP result?)

Hmm: Something interesting about hyperfactorials: k * hyperfactorial(a)^n + 1 cannot be prime when a is odd and when n is divisible by 2. Let's try even a; n is odd.
Conjecture debunked: 1286 * hyperfactorial(8)^3 + 1 is prime.

Next conjecture: It applies to all odd integers only?
Debunked: 348 * hyperfactorial(9)^4 + 1 is prime; 261 * hyperfactorial(9)^6 + 1 is prime.
Next: Applies to odd primes:
Debunked: 811 * hyperfactorial(13)^4 + 1 is prime.
Surprisingly, I found that all cases were composites when I tested a = 11. Pseudo-sierpinski number, anyone?