VFYPR is uses a combination of methods to verify primes: Factorization of N − 1, factorization of N + 1, and the APRCL method. The implementation of the APRCL algorithm is a more-or-less direct conversion of APRT-CLE from UBASIC to C, and somewhat extended to handle numbers of up to about 3000 digits.
You enter numbers to be tested either via the keyboard or in a file called VFYPR.INP. You can also supply other parameters. VFYPR processes the numbers according to the parameters specified and for each number it will probably return one of the answers '*** N is prime!', meaning that (if the program has been used correctly) N is a true, proven prime, or '*** N is composite'.
Set up this file with numbers to be tested, each on a separate line. A zero terminates the list. Arithmetical expressions may be used. If this file does not exist, you will be prompted to enter a number via the keyboard.
Set up this file with a list of verified primes to try as possible factors of N^2 − 1. Put each number on a separate line. A zero terminates the list. It is vitally important that VFYPR.PRM contains only primes that have been verified. Otherwise the algorithm is not valid.
If a number in VFYPR.PRM does not divide (N + 1)(N − 1), it is ignored.
File created by VFYPR. Results are written here. Echoed on the screen.
File created by VFYPR. Journal. Used only for debugging.
File created by VFYPR. List of prime factors of (N + 1)(N − 1) found by the program.
File created by VFYPR. Controls the restart mechanism. This file contains information that was saved by the program for the last number tested. If the program program was interrupted, you can get it to carry on from where it left off by using the 'r' option.
VFYPR.EXE r k a h C D J F100000 S100000
r: Restart unfinished work, if any.
k: Get input from keyboard. Ignore VFYPR.INP file.
a: APRCL test only. Do not use factors of (N − 1)(N − 1).
h: Halt if N is not prime.
C: Do the current segment only.
D: Debug mode. Does various debugging functions.
J: Journal mode. Logs much diagnostic data to the journal.
F#: Specify an upper limit for small factors of (N − 1)(N − 1).
S#: Specify a minimum value of S for the APRCL test.
Every so often during a long run parameters are saved so that the test can be resumed without too much loss of work. If your computer crashes, or you want to stop a test for some other reason, when you restart VFYPR with option 'r', it will carry on from the last checkpoint.
To stop the program gracefully, press upper-case 'Q' on the keyboard. Wait for the 'VFYPR stopped' message to appear. Usually this takes a few seconds but if N is large, it could be several days. Then press 'X'. If you change your mind and want to continue, press ENTER.
Pausing the program in this way can be useful. It temporarily closes the log (VFYPR.DAT) thereby allowing you to view it with your favourite editor before restarting the program.
1. If (N + 1)(N − 1) has a lot of small prime factors, run VFYPR.EXE without any options. The small factors will get detected and used for the BLS tests.
2. If there is nothing special about N, you can consider doing a pure APRCL test. Use option 'a': VFYPR.EXE a. This saves the trouble of trial-dividing (N + 1)(N − 1) by small primes.
3. If (N + 1)(N − 1) has known, large prime factors, either by design or because you have extracted them: First verify that the factors are true primes. Then put them in VFYPR.PRM and run VFYPR.EXE without any options.
VFYPR searches VFYPR.PRM first, then it does the factor 2, and if it still needs more factors of (N + 1)(N − 1), it tries small primes up to a limit which you can specify by the 'F' parameter.
I repeat the disclaimer stated above: If a number in VFYPR.PRM is used by VFYPR as a factor of (N + 1)(N − 1) and is not a true, proven prime, the algorithm is not valid.
4. It is possible to split the APRCL tests into segments that can be run on separate computers.
Start VFYPR with option 'C' and let it run until the APRCL main tests for p = 2 start to appear. Pause VFYPR by pressing 'Q' and waiting for the 'VFYPR stopped' message to appear. Save VFYPR.INI. Make a note of the parameter T, which is the second number printed in the 'Parameters saved' message. Restart VFYPR by pressing ENTER. It will eventually stop when it has completed the APRCL main tests for p=2.
Meanwhile, make several copies of the saved VFYPR.INI file. The last three numbers (which are all together on the last line of VFYPR.INI) must be set for each prime factor p of T according to the following scheme
2 1 0 : APRCL main tests for p = 3,
3 1 0 : APRCL main tests for p = 5,
4 1 0 : APRCL main tests for p = 7,
5 1 0 : APRCL main tests for p = 11,
6 1 0 : APRCL main tests for p = 13,
7 1 0 : APRCL main tests for p = 17.
Make a final copy of the saved VFYPR.INI with the first number (in the first line) set to
3 : for an APRCL-only test,
4 : otherwise,
and the last three numbers set to
1 0 0
Do not alter any other numbers in VFYPR.INI. On each computer set up one of the VFYPR.INI files and start VYRPR with parameters 'Cr' (or 'Cra' for an APRCL-only test). As each computer completes its work, it will end with the 'Cannot tell' message. This is OK. However, once you have gathered together the data from all the separate VFYPR.DAT files, you will have your primality proof.
5. VFYPR will accept arithmetical expressions in VFYPR.INP, VFYPR.PRM and 'stdin'.
Expressions consist of decimal digits, '+', '-', '*', '/' (integer division with truncation towards zero), '@' (modulo), '^' (exponentiation), '!' (factorial), '#' (prime product), 'q' (integer square root) and brackets to a reasonable level.
A semicolon terminates the expression. '+' and '-' can be prefixes; '-' negates what follows; '@' always gives a non-negative result; x# is the product of the primes up to and including x; qx = [x1/2].
The order of precedence is '(' and ')'; '!' and '#'; prefix '+', prefix '-' and 'q'; '^'; '*', '/' and '@'; '+' and '-'. Exponentiation is left-to-right.
1. Do not use VFYPR for N > 10300000. The program is unreliable beyond this limit.
2. Although Carmichael numbers are quickly declared composite by a pure APRCL test, a hybrid test sometimes appears to loop forever trying to find a number a for which gcd(a(N − 1)/2 − 1, N) = 1.
3. Long lines written to VFYPR.DAT seem to confuse some editors.
4. Bug! Under Win-Me, VFYPR crashes when it tries to read file VFYPR.PRM if that file does not exist.
'*** VFYPR v F_max=Fmax S_min=Smin h=h a=a
C=C J=J D=D'
'N = N'
This appears at the beginning of a test. The version number of the program is v; The parameters are Fmax, Smin, h, a, C, J and D; N is the number being tested.
'Fail: 3^(N-1) not = 1 (mod N): R20=r'
The preliminary probable-primality test has failed; r is the last twenty decimal digits of 3N − 1 mod N; N is composite.
In this message and others, below, the 'R20' number provides you with a convenient way of challenging the integrity of the program. You are invited to repeat the relevant computation with your own software and see if you obtain the same result.
'Factor: f^e divides N - 1'
'Factor: f^e divides N + 1'
A factor fe of N − 1 or N + 1 was found, either by searching VFYPR.PRM, or by trying out small primes.
'Factorization results: F1=a F2=b'
'F1=F1'
'F2=F2'
Summary of the search for factors of N2 − 1; a = log(F1)/log(N), b = log(F1)/log(N), F1 is the product of all the known prime factors of N − 1, F2 is the product of all the known prime factors of N + 1.
'Pass: gcd(a^((N-1)/f) - 1, N) = 1: R20=r'
The BLS test for factor f of N − 1 was successful; r is the last 20 decimal digits of a(N − 1)/f − 1 mod N.
'Fail: gcd(a^((N-1)/f) - 1, N) not = 1: R20=r'
The BLS test for factor f of N − 1 was not successful; r is the last 20 decimal digits of a(N − 1)/f − 1 mod N. If the gcd is less than N, N is composite. Otherwise we need to try a different value of a.
'Pass: a^(N-1) = 1 (mod N): R20=1'
The main BLS test for N − 1 was successful.
'Fail: a^(N-1) not = 1 (mod N): R20=r'
The main BLS test for N − 1 was not successful; N is composite; r is the last twenty decimal digits of aN − 1 mod N.
'Pass: gcd(U{(N+1)/f}, N) not = 1: d=d p=p q=q R20=r'
The BLS test for factor f of N + 1 was successful; r is the last 20 decimal digits of U(N + 1)/f mod N. The Lucas sequence Ui is defined by U0 = 0, U1 = 1, Ui + 2 = p*Ui + 1 − q*Ui and its discriminant is d = p^2 − 4*q, (d/N) = −1.
'Fail: gcd(U{(N+1)/f}, N) not = 1: d=d p=p q=q R20=r'
The BLS test for factor f of N + 1 was not successful; r is the last 20 decimal digits of U(N + 1)/f mod N for the Lucas sequence Ui defined as above. If the gcd is less than N, N is composite. Otherwise we must try a different Lucas sequence with the same discriminant, d.
'Pass: U{N+1} = 0 (mod N): d=d p=p q=q R20=0'
The main BLS test for N + 1 was successful for the Lucas sequence Ui defined as above.
'Fail: U{N+1} = 0 (mod N): d=d p=p q=q R20=r'
The main BLS test for N + 1 was not successful for the Lucas sequence Ui defined as above; N is composite; r is the last twenty decimal digits of UN + 1.
'Pass: (F1+1)^2 > N: R20=r'
Sufficient BLS tests have passed for factors of N − 1; N is prime; r is the last twenty digits of (F1 + 1)2 mod N.
'Pass: (F2-1)*(F2+1) > N: R20=r'
Sufficient BLS tests have passed for factors of N + 1; N is prime; r is the last twenty digits of (F2 − 1)*(F2 + 1) mod N.
'BLS tests passed: F1=a F2=b'
The conditions of Pocklington's theorem are satisfied with F1 = Na approximately. The conditions of Morrison's theorem are satisfied with F2 = Nb approximately. Hence if d is a factor of N, then d = 1 (mod F1) and d = ±1 (mod F2).
'APRCL test'
'T=T'
'S=S'
We are beginning the APRCL test with the parameters indicated.
'APRCL main test (i) at level l for p=p'
We are beginning the APRCL tests for prime p. It is the i-th p to be tested. Level l refers to the value of T; it is the l-th in a fixed list of values used by the program.
'Restarting APRCL main test at (i j)'
We are restarting the APRCL test from the i-th prime, p, and the j-th prime, q.
'APRCL L_p condition satisfied'
For each prime p we tell you when this important part of the APRCL primality test has been successful.
'APRCL main test (i j) done: p=p q=q k=k g=g h=h'
The APRCL test for the i-th prime, p|T, and the j-th prime, q|S, has completed successfully; pk is the highest power of p that divides q − 1, g is the primitive root of q that defines the character modulo q of order pk that was used for the test. The result of the Jacobi sum calculation was (ζpk)h = e2 π i h/pk.
'APRCL Fail: Result for p=p q=q k=k g=g is not a power of zeta_n'
The APRCL test for primes p and q, pk||q − 1, did not result in an n-th (= pk-th) root of unity. Therefore N is composite.
'APRCL Fail: zeta_n exponent Hj=h for p=p q=q k=k g=g is not equal to Hc=c'
The APRCL test for primes p and q, pk||q − 1, did result in an n'th root of unity, e2 π i h/n, n = pk. But it was not the correct root. It should have been e2 π i c/pk. Therefore N is composite because condition Lp is not satisfiable.
'APRCL Fail: q^((N - 1)/2) != -1 (mod N): R20=r'
We have found N to be composite during the APRCL test; r is the last twenty digits of q(N − 1)/2 mod N.
'APRCL main test (i j) for p=p q=q not needed'
For good reasons VFYPR chooses its primes p and q in the same way as Yuji Kida's UBASIC program APRT-CLE. However, in VFYPR, the parameter S is coprime to F1 F2 (from the BLS tests). This message appears whenever a q that does not divide S is selected and condition Lp is satisfied.
'Retry'
The APRCL tests for all the q's for a prime p have been done, but condition Lp is not satisfied. We must get more primes q (for which p|q − 1) and continue testing until condition Lp is met.
'Retry from the beginning'
The APRCL tests for all the q-s for a prime p have been done, but condition Lp is not satisfied. We must get more primes q (for which p|q − 1) and continue testing until condition Lp is met. The difference between this and the last situation is that we have used up all the q-s for the current value of T. We need to go to the next level for a bigger value of T.
'APRCL tests for p=p completed'
The APRCL tests for all the q-s for the prime p have been done.
'APRCL divisor test T=T, S=S'
An APRCL-only test is in operation. All the (p, q) tests have been done. It now remains to trial-divide N by all possible divisors d = Ni (mod S), 0 < i < T.
'Restarting APRCL divisor test at i/T'
An APRCL-only test is in operation. The APRCL divisor test is restarting.
'APRCL divisor test passed: t/T'
An APRCL-only test is in operation. The APRCL divisor test has completed. No divisors d = Ni (mod S), 0 < i < T, have been found. If S2 > N, N is prime. The ratio T/t is a small integer, usually 1. The search for divisors Ni (mod S) can stop when i = t because Nt = 1 (mod S).
'Main divisor test: F1=a F2=b G=g S=s T=T'
'G=G'
BLS tests and APRCL tests are done. The next stage is to trial-divide all d such that d = 1 (mod F1), d = e (mod F2) for e = −1 or 1, and d = Ni for 0 < i < T. Approximately, F1 = Na, F2 = Nb, S = N s and G = F1 F2 S/2 = N g.
'Restarting main divisor test at i/T'
The main divisor test is restarting.
'Main divisor test passed: t/T'
The main divisor test has finished without finding a proper divisor of N. The ratio T/t is a small integer, usually 1.
'Final divisor test: F=F G=G H=H t=t a=a'
Let d be a prime divisor of N. When we arrive here we know that d > G > N1/3. However, G < N1/2, for otherwise N would be prime. If F1 > F2, F = F1, t = −1, a = (N/G + G − (r F + 2))/(2 F2) + 1, where R = (N − 1)/F = 2 F s + r, 0 < r < 2 F, and we use Theorem 1 to complete the primality proof. Otherwise F = F2, t = 1, a = (N/G − G + |r F − 2|)/(2 F2) + 1, where R = (N + 1)/F = 2 F s + r, |r| < F, and we use Theorem 2 to complete the primality proof.
'Restarting final divisor test at m/n'
The final divisor test is restarting.
'Final divisor test passed: m/n r=r i=i'
The final divisor test is complete. No divisors d > N1/3 have been found. During this stage VFYPR tested m = n candidate divisors resulting from the application of Theorem 1 or Theorem 2. Of the n possible divisors, r were real and i were integers.
'Parameters saved: r, t, i, j, k, n, s'
VFYPR has taken a checkpoint at a stage of the algorithm indicated by r, t, i, j and k. It is the n-th parameter saving and it (probably) happened s seconds after the (n − 1)-th saving.
'VFYPR stopped: Press X to terminate, anything else to continue'
This appears if you stop the program, or if something has gone wrong. Pressing X terminates the program.
'Error ...'
There was a malfunctioning of the program as indicated (in terms that are understandable by me) in the rest of the message. Usually this type of message reports a condition that is impossible. If it appears, then it is something I would like to know about, and you will be invited to e-mail relevant information to me. But note that the e-mail address hard-coded in the program is wrong! Send it to anthony.d.forbes@gmail.com instead.