[MPU - Primality Certificate] Version 1.0 # We should allow base 10, base 16, and base 62. Base 10 is the default. Base 10 # This is the N value we're proving. Proof for: N 8087094497428743437627091507362881 # The following types allow a simple chain: # Pocklington # BLS3 # BLS15 # ECPP # Small # These could result in a tree: # Lucas # BLS5 # BLS7 # # Types ECPP3 and ECPP4 are from Primo, and can be easily translated into # a type ECPP. We include them here rather than convert because they save # quite a bit of space and we may want to generate them ourselves someday. # I remain dubious about including them, so it is possible they will go away # in the format and we'll just have the converter/verifier do the conversion. # # MPU will generate types: BLS3, BLS15, ECPP, BLS5, Small. # Primo (converted) will generate types: Pocklington, BLS15, ECPP3, ECPP4. # Lucas is included for completeness. # I no longer use BLS7 so will not include it. # BLS## stands for theorem ## in the paper: # "New Primality Criteria and Factorizations of 2^m +/- 1" by # Brillhart, Lehmer, and Selfridge, Mathematics of Computation, 1975. # which includes 21 theorems related to N-1, N+1, and hybrid primality proofs. # The paper is often referred to as BLS75, and is highly recommended reading. # I allow N or any Q smaller than 2^64 to implicitly construct a "Small" # certificate. So once we have a Q of <= 2^64, we can run a deterministic # test to prove its primality. One of the many BPSW variants works for this, # or 7 M-R tests with bases 2, 325, 9375, 28178, 450775, 9780504, 1795265022. # Hence if we have Q values <= 2^64, the verifier needs to do its test, and # the certificate can leave out an explicit proof for the Q. This is done # to prevent a few Lucas, BLS5, etc. type tests from creating a swarm of # "Small" certificates for each little factor. Type BLS15 N 8087094497428743437627091507362881 Q 175806402118016161687545467551367 LP 1 LQ 22 # Note: Primo type 2 can map to this, though this allows Q to be # smaller. ( prevR->N, R->Q, S->M, Q->(LP,LQ) ) # Primo condition a is implied by Q odd # Primo condition c is stricter than required by BLS15. # Primo conditions e and f relate to the Lucas code # Primo condition g is not required # Verify: Q is odd # Verify: Q > 2 # Verify: Q divides N+1 # Let: M = (N+1)/Q # Verify: MQ-1 = N # Primo d # Verify: M > 0 # Primo b # Verify: 2Q-1 > sqrt(N) # Primo c (less strict) # Let: D = LP*LP - 4*LQ # Verify: D != 0 # Verify Jacobi(D,N) = -1 # Primo h # Verify V_{m/2} mod N != 0 # Primo j # Verify V_{(N+1)/2} mod N == 0 # Primo i # Then N is prime if Q is prime. Type ECPP N 175806402118016161687545467551367 A 96642115784172626892568853507766 B 111378324928567743759166231879523 M 175806402118016177622955224562171 Q 2297612322987260054928384863 X 3273750212 Y 82061726986387565872737368000504 # Generic ECPP / AKGM block # A and/or B can be -1, so mod them. # Let A = A % N # Let B = B % N # Verify: N > 0 # Primo b # Verify: gcd(N, 6) = 1 # Primo a # Verify: gcd(4*a^3 + 27*b^2, N) = 1 # Primo i # Verify: Y^2 mod N = X^3 + A*X + B mod N # Primo j # Verify: M >= N - 2*sqrt(N) + 1 # Primo g # Verify: M <= N + 2*sqrt(N) + 1 # Primo h # Verify: Q > (N^(1/4)+1)^2 # Primo f # Verify: Q < N # Primo e # Verify: M != Q # Verify: Q divides M # Note: EC(A,B,N,X,Y) defines the elliptic curve Y^2 = X^3 + A*X + B, mod N # with operations defined in affine coordinates. # Let POINT = (M/Q) * EC(A,B,N,X,Y) # Verify: POINT is not the identity # Primo k # Let POINT = Q * POINT (or M * EC(A,B,N,X,Y)) # Verify: POINT is the identity # Primo l # Then N is prime if Q is prime. Type BLS3 N 2297612322987260054928384863 Q 16501461106821092981 A 5 # Note: This is similar to Pocklington, but Q can be smaller. # Verify: Q odd # Verify: Q > 2 # Verify: Q divides N-1 # Let: M = (N-1)/Q # Verify: MQ+1 = N # Verify: M > 0 # Verify: 2Q+1 > sqrt(N) # Verify A^((N-1)/2) mod N = N-1 # Verify A^(M/2) mod N != N-1 # Then N is prime if Q is prime. Type BLS5 N 8087094497428743437627091507362881 Q[1] 98277749 Q[2] 3631 A[0] 11 ---- # Note: This also covers generalized Pocklington # Note: We have to have N-1 factored to (N/2)^1/3 # Note: A line starting with - is required at the end. # Verify: N > 2, N odd # For each i (0-max): # Q[0] = 2 # 2 is always a factor of n-1 # A[i] = 2 unless specified # Verify: Q[i] > 1, Q[i] < N-1 # Verify: A[i] > 1, A[i] < N # Verify: Q[i] divides N-1 # Let: F = N-1 divided by each Q[i] with multiplicity # (i.e. if Q[i] evenly divides N-1 3 times, then divide it out 3 times) # Let: R = (N-1)/F # Verify: F is even # Verify: gcd(F, R) = 1 # Let: s = integer part of R / 2*F # Let: r = fractional part of R / 2*F # Let: P = (F+1) * (2*F*F + (r-1)*F + 1) # Verify: n < P # Note: The next condition is trivially met if F >= R, # as is the case with Pocklington. # Let: rt = r^2 - 8s # Verify: s = 0 OR rt not a perfect square [e.g. floor(sqrt(rt))^2 != rt] # For each i: # Verify: A[i]^(N-1) mod N = 1 # Verify: gcd(A[i]^((N-1)/Q[i])-1, N) = 1 # Then N is prime if each Q is prime. Type Lucas N 10384593717069655257060992658440473 Q[1] 2 Q[2] 3 Q[3] 13 Q[4] 379 Q[5] 87820459687010818424506060639 A 41 # Note: All factors of N-1 are listed # Verify: A > 1 and A < N # Verify: N-1 has only factors Q (to some multiplicity). # Verify: A^(N-1) mod N = 1 # Verify for each Q: # Q > 0 # Q < N-1 # Q divides N-1 # A^((N-1)/Q) mod N != 1 # Then N is prime if each Q is prime. Type Pocklington N 2297612322987260054928384863 Q 16501461106821092981 A 5 # Note: This is Primo type 1 ( prevR->N, R->Q, S->M, B->A ) # verify: Q divides N-1 # let: M = (N-1)/Q # Verify: M is even # Primo a # Verify: M > 0 # Primo b # Verify: M < Q # Primo c # Verify: MQ+1 = N # Primo d # Verify: A > 1 # Primo e # Verify: A^(N-1) mod N = 1 # Primo f # Verify: gcd(A^M - 1, N) = 1 # Primo g # Then N is prime if Q is prime. Type ECPP3 N 33863876771064627047864880693347 S 8929168182 R 3792500721324706215857 A -30 B 56 T 0 # From Primo. Experimental, may go away. # Verify: |A| <= N/2 # Verify: |B| <= N/2 # Verify: T >= 0 # Verify: T < N # Let: L = (T^3 + A*T + B) mod N # Let: A = (A * L^2) mod N # Let: B = (B * L^3) mod N # Let: X = (T*L) mod N # Let: Y = (L^2) mod N # Let: Q = R # Let: M = R*S # Continue as type ECPP. Type ECPP4 N 346908375519289784739191985209489924762236002832827279935279239073873837063 S 26591618 R 13045779144363828659812726897983038292936490633310834005307717308699 J -4092776160830678382137043215242735918658074999545950247507675196218505248 T 4 # From Primo. Experimental, may go away. # Verify: |J| <= N/2 # Verify: T >= 0 # Verify: T < N # Let: A = 3 * J * (1728 - J) # Let: B = 2 * J * (1728 - J)^2 # Let: L = (T^3 + A*T + B) mod N # Let: A = (A * L^2) mod N # Let: B = (B * L^3) mod N # Let: X = (T*L) mod N # Let: Y = (L^2) mod N # Let: Q = R # Let: M = R*S # Continue as type ECPP. Type Small N 5791 # Verify: N < 2^64 # Verify: N is prime using BPSW or deterministic M-R tests # Experimental, not used: #Type BLS7 #N 10384593717069655257060992658440473 #Q[1] 87820459687010818424506060639 #Q[2] 379 #Q[3] 13 #Q[4] 3 #Q[5] 2 #A[1] 2 #A[2] 2 #A[3] 2 #A[4] 19 #A[5] 5 #B 10000 #AR 2 # Verify for each i: # Q[i] > 1, Q[i] < N # A[i] > 1, A[i] < N # Q[i] divides n-1 # Let: F = product of all Qs # Let: R = N/F # Verify: F is even # Verify: gcd(F, R) = 1 # Verify: F has no factors smaller than B (this may be time consuming) # Let: s = integer part of R / 2*F # Let: r = fractional part of R / 2*F # Let: P = (F*B+1) * (2*F*F + (r-B)*F + 1) # Verify: n < P # Let: rt = r^2 - 8s # Verify: s = 0 OR rt not a perfect square [e.g. floor(sqrt(rt))^2 != rt] # For each i: # Verify: A[i]^(N-1) mod N = 1 # Verify: gcd(A[i]^((N-1)/Q[i])-1, N) = 1 # Verify: AR^(N-1) mod N = 1 # Verify: gcd(AR^((N-1)/R)-1, N) = 1 # Then N is prime if each Q is prime.