File Associations

---

When running, PRIMO works with the following text files:
Primo-xxxxxxxxxxxxxxx.cr........ Certification Report file
*.in............................ Input file (Integer to test)
Primo-xxxxxxxxxxxxxxx-nnn.out... Output file (Primality certificate)
Primo-xxxxxxxxxxxxxxx.tr........ Task Report file
xx..xx is a unique identifier that allows to identify all the files created during batch processing.
nnn indicates the index (when batch processing) of the tested integer.
In order to open these files with your favorite text editor, you should create an association File extension - Editor for the extensions .cr, .in, .out and .tr. If you do not create associations, PRIMO will use NotePad by default.

---

First Session

---

Run PRIMO.
Click on the Certification button.
In the Certification page, click on the Load file(s)... button. Select the work directory and double-click on first.in.
When the certification is done, a short report is displayed in the editor of the Task Report page. To open a results text file, double-click on the relevant item.

---

Contents

Buttons

---

Help	Open the documentation.
About Primo	Open the About dialog box.
New input file	Create a new empty input file.
Open a Primo text file	Open a file list box with which you can select PRIMO text files: input, output, task report and certification report. These files are open with the text editor you associated with their extensions (or with NotePad if there is no association).
Quit	Close PRIMO.

---

Check box

---

Idle	When checked, the PRIMO process priority is set to "idle", otherwise it is set to "normal". The value can be changed while running a task (certification or verification). Default value = Unchecked (Normal priority)

---

Contents

The Task Report page contains an editor used to display certification and verification reports.

Report Editor

---

When an entry in the report contains the name of a PRIMO text file, you can open the file by double-clicking on the item (alternately, you can select the item with the Arrow keys and hit the Return key to open the file).
The editor content is automatically saved to a task report file (text file).

---

Contents

The Certification page is a dialog box that allows to perform the certification of integers in PRIMO input files (and also to resume aborted certificates). Loading .in files starts certifications. Loading .tmp files restarts aborted certifications.
The certificates are automatically saved to output files, in the directory that contains the input files.
While certifying, PRIMO creates and updates temporary files having the .tmp extension. Do not modify them. If you want to edit them (they are text files), make copies and edit those copies. If ever a .tmp file is modified (some editors add invisible codes), all the work done may be lost!
See also: What is a certificate?

Setup

---

Certification reports

When checked, PRIMO creates certification report files. Default value = Checked

Double file management

When checked, even in case of problem when PRIMO is writing on a disk (OS crash, outage, etc.), there should always be at least one valid file on the disk among these three possible ones : .tmpnew, .tmp or .tmpold. Of course, in order to restart PRIMO with one of these files, its extension has to be set with .tmp (if need be). This option is useful with very big candidates only. Default value = Unchecked

---

Status

---

Elapsed time	Running time of the certification.
Number	Number (in the input file list) of the integer that is currently being tested.
Phase	Number of the current phase (1 or 2). The Phase 1 consists in finding a sequence of pseudoprimes. The Phase 2 consists in building and factoring class polynomials and in computing elliptic curves and points (which ones prove that the sequence of pseudoprimes found during Phase 1 is in fact a sequence of primes).
Test	Number of the current test. The value may decrease due to backtracking.
Run	Number of the current run (max = 6)
Bits	Indicates the binary size of the integer currently tested.
Status	Miscellaneous information regarding the current status of a certification.

---

Buttons

---

Load	Load files and start certifications (and/or restart aborted certifications). The selected files are always processed in alphabetical order.
Abort	Allow to abort a certification. When a certification is aborted, a partial certificate is saved to a file having the .tmp extension. To restart the certification, just load this file.

---

Contents

The Verification page is a dialog box that allows to verify and to sign certificates. Checking can be aborted and resumed (PRIMO restarts from the last test not yet processed).
The certificates are always verified and signed while certifying.
See also: What is a certificate?

Setup

---

Check signatures only

When not checked, PRIMO always verifies the certificate and signs it. If the certificate is already signed, the existing signature is deleted before starting the verification. When checked, PRIMO tries to check the signature only (this allows to quickly reject invalid certificates). If there is no signature section then it verifies the certificate and signs it. Default value = Checked

Double file management

When checked, even in case of problem when PRIMO is writing on a disk (OS crash, outage, etc.), there should always be at least one valid file on the disk among these three possible ones : .outnew, .out or .outold. Of course, in order to restart PRIMO with one of these files, its extension has to be set with .out (if need be). This option is useful with very big candidates only. Default value = Unchecked

---

Status

---

Elapsed time	Running time of the verification.
Certificate	Number (in the output file list) of the certificate that is currently being verified.
Test	Number of the current test.
Bits	Indicates the binary size of the integer currently checked.
Status	Miscellaneous information regarding the current status of a verification.

---

Buttons

---

Load	Load files and start verifications. The selected files are always processed in alphabetical order.
Abort	Allow to abort a verification.

---

Contents

A primality certificate produced by PRIMO is a sequence of tests. Each test, except the final one, proves that an integer, called N, is prime assuming a smaller integer, called R, is also prime. Since the R value of a test is used as the N value of the following test, the primality of the last R value of a certificate proves the primality of the candidate.
PRIMO makes use of up to four different tests.
Note: In what follows, N is always a positive odd integer greater than 65536.

Strong Pseudoprime Test

---

In a certificate, this test is identified with Type = 0

Assuming N < 34 * 10^13,
if N is a strong pseudoprime to the bases 2, 3, 5, 7, 11, 13 and 17 then N is prime.

The first number which is a strong pseudoprime to these seven bases, but not a prime, is larger than 34 * 10^13.

---

N-1 Test

---

In a certificate, this test is identified with Type = 1

Assuming N = S * R + 1 with R prime and S < R,
if there exists an integer B > 1 such that
  B^(N-1) = 1 mod N
  gcd(B^S - 1, N) = 1
then N is prime.

---

N+1 Test

---

In a certificate, this test is identified with Type = 2

Assuming N = S * R - 1 with R prime and S < R,
if there exists a Lucas sequence V[i], with parameters P and Q, such that
  gcd(P, Q) = 1
  Jacobi(P² - 4Q, N) = -1
  V[(N+1)/2] = 0 mod N
  V[S/2] <> 0 mod N
then N is prime.

The parameter P is not displayed in PRIMO certificates. When Q is even, P = 1 ; when Q is odd, P = 2.

---

Elliptic Curve Test

---

In a certificate, this test is identified with Type = 3 or with Type = 4

Assuming M = S * R, with S > 1, R prime, R > (N^(1/4) + 1)^2,
if there exist a non-singular elliptic curve y^2 = x^3 + ax + b modulo N, with order M, and a point P = (x, y) on this curve such that
  P * S <> Identity
  (P * S) * R = Identity
then N is prime.

Type = 3
The 3 parameters A, B and T, reported in PRIMO certificates, allow to quickly compute the required curve and point:
  L := (T^3 + A*T + B) mod N
  a := (A * L^2) mod N
  b := (B * L^3) mod N
  x := (T * L) mod N
  y := (L^2) mod N

Type = 4
The parameter J allows to compute A and B as defined with Type = 3:
  A := 3 * J * (1728 - J)
  B := 2 * J * (1728 - J)^2

---

Contents

In the Certification page, click on the Load file(s) and start certification(s) button. Select the .tmp file created when aborting the certification.
That’s all.

Contents

An internal error may be raised by PRIMO for mainly two reasons: a hardware failure or a PRIMO bug.
In case such an error occurs, try first to redo what you were doing. If the error still occurs, thanks to report the problem with the most possible details: OS used, processor type, partial certificate obtained, etc. as well as a description of the problem, mail to primo (at) ellipsa (dot) eu

Contents

A PRIMO input file is a text file (its syntax is similar to the one of Windows ini files) that should contain an integer to test. This integer should be greater than 65536 and less than 2^131072 (note that the greatest number ever certified with Primo is smaller than 2^28552).
The extension name of an input file should always be .in.

Syntax

---

An input file has syntax examplified by the text within the horizontal bars:
-------------------------------------------------------------------------------
; any comment you want after a semi-colon
[Candidate]
N=
-------------------------------------------------------------------------------
The file may contain any number of blank lines.

Candidate expressed to the base 10
The number (or the expression) that follows N= should be written on a single line.
There should be no character (Space, Tab, or else) before the first character of the section [Candidate], before N= or before a semicolon ;
Expressions are allowed:
  The alphabet is + - * / ^ ! # ( ) 0 1 2 3 4 5 6 7 8 9
  There should be NO SPACE in a number or before ! or #
  Factorial(10) should be written 10!
  Primorial(13) should be written 13#
  ! also stands for Multi-Factorial, i.e., 23!7 = 23*16*9*2, in that case there should be NO SPACE before or after !
  ^ is associative on the left, i.e., a^b^c = (a^b)^c
N=10^999 + 7, N=3229# + 1 or N= ((3229#) + 1) are valid
N=32 29# + 1 is not valid, there is a space between two digits

Candidate expressed to the base 16
To work with a number expressed to the base 16, use the key N$= instead of N=
There should be no character (Space, Tab, or else) before the first character of the section [Candidate], before N= or before a semicolon ;
Expressions are not allowed.

---

4 examples of valid input files

---

;PRIMO Input File [Candidate] N=1384435372850622112932804334308326689651568940268408537

;PRIMO Input File ;Number expressed to the base 16 [Candidate] N$=cc8fa1481b11589c04f066367b204e09132082838aef805f207555505e690153

;PRIMO Input File ;This number will be rejected, it is less than 65536 [Candidate] N=997

;PRIMO Input File ;Expression [Candidate] N=10^700 + 7

---

Contents

A primality certificate is a sequence of integers that satisfy the requirements of various theorems (For more information concerning the tests used, see What is a primality certificate?). With the primality certificate of an integer, an independent verifier can quickly check the primality of this integer.
Primality certificates are automatically saved to output files (which are text files), in the directory that contains the input file.

Example of certificate

---

[PRIMO - Primality Certificate] Version=3.0.9 WebSite=http://www.ellipsa.eu/ Format=3 ID=B2D6C052498F2 Created=12/25/2009 00:00:00 AM TestCount=7 Status=Candidate certified prime [Candidate] File=C:\primo\work\first.in N$=E74451F3DD74E0045407CF480C2A5DA72A57427444ED9 HexadecimalSize=45 DecimalSize=55 BinarySize=180 [Running Times] Initialization=0.00s 1stPhase=0.01s 2ndPhase=0.01s Total=0.02s [1] Type=3 S$=30B73FD7A R$=4BF4CBACF02AB9B134C2B4C499CC73301A5E9 A$=-1C4B8382FDCBBBEA5B211BD307615E17DD905ED42F69D B$=0 T$=1 [2] Type=3 S$=12268EF R$=42F4D55D4B18D2894579419DB0DB139 A$=-108 B$=69E T$=2 [3] Type=1 S$=368E179DF8 R$=13A317FA2002F1E4803799 B$=2 [4] Type=1 S$=48 R$=45D21C5CE398B165561B B$=2 [5] Type=3 S$=7D42A6 R$=8EB21868AEE181 A$=-1E B$=38 T$=0 [6] Type=1 S$=20580 R$=4696ED2829 B$=2 [7] Type=0 [Signature] 1$=67B6BCF0700C92F36BBBD4CC32A1D9BD880323B4 2$=1D845A7D5B774BCECDB5D70070BA063B991816F8

Running time obtained with an AMD XP 3200+ processor

---

Details

---

[PRIMO - Primality Certificate]	Header section
Version=	PRIMO version
WebSite=	Homepage of PRIMO
Format=	Certificate format
ID=	Unique identifier that allows to know all files created during a given task (associated files always have the same identifier)
Created=	Creation date of the certificate
TestCount=	Total number of tests in the certificate
Status=	Status of the certificate
[Candidate]	Candidate section
File=	File name of the candidate
Expression=	Candidate expressed as a formula (if any in the input file)
N$=	Candidate (always expressed to the base 16)
HexadecimalSize=	Hexadecimal size (base 16) of the candidate
DecimalSize=	Decimal size (base 10) of the candidate
BinarySize=	Binary size (base 2) of the candidate
[n]	Test section  n is the number of the test
Type=	Type of the test 0: Strong pseudoprime 1: N-1 2: N+1 3: Elliptic curve 4: Elliptic curve
S$=	S (expressed to the base 16)
R$=	R (expressed to the base 16)
A$=	A (expressed to the base 16)
B$=	B (expressed to the base 16)
J$=	J (expressed to the base 16)
T$=	T (expressed to the base 16)
Q$=	Q (expressed to the base 16)
[Signature]	Signature section
1$=	1st part of the signature of a certificate (160 bits)
2$=	2nd part of the signature of a certificate (160 bits)

---

Contents

After certifications or verifications, PRIMO opens the Task Report Page and displays miscellaneous information about the work done.
Task reports are automatically saved to .tr files. These text files are always created in the directory that contains the input files (certifications) or the output files (verifications).

Example of task report file

---

[PRIMO - Task Report] Version=3.0.9 WebSite=http://www.ellipsa.eu/ Task=Certification ID=B2D6D00030D30 Created=12/25/2009 00:00:00 AM [Common] Path=C:\primo\bench\1024 bits\ Selected=3 Processed=3 Certified=3 Candidate #1=Certified, 5.72s Candidate #2=Certified, 6.98s Candidate #3=Certified, 6.60s [Candidate #1] Input=prime01.in Output=Primo-B2D6D00030D30-001.out Status=Candidate certified prime [Candidate #2] Input=prime02.in Output=Primo-B2D6D00030D30-002.out Status=Candidate certified prime [Candidate #3] Input=prime03.in Output=Primo-B2D6D00030D30-003.out Status=Candidate certified prime

---

Contents

A certification report contains extra information regarding a certification.
Certification reports are saved to .cr files (which are text files), in the directory that contains the input files.

Example of certification report

---

[PRIMO - Certification Report] Version=3.0.9 ID=B2D6C052498F2 Created=12/25/2009 00:00:00 AM Certificate=C:\primo\work\Primo-B2D6C052498F2-001.out TestCount=7 [Backtrack] Count=0 [1] Type=3 Run=1 Gain=33 D=-4 H=1 G=1 [2] Type=3 Run=1 Gain=24 D=-11 H=1 G=1 [3] Type=1 Run=1 Gain=38 [4] Type=1 Run=1 Gain=6 [5] Type=3 Run=1 Gain=23 D=-8 H=1 G=1 [6] Type=1 Run=1 Gain=17 [7] Type=0 Run=1 Gain=39

Details

---

[PRIMO - Certification Report]	Header section
Version=	PRIMO version
WebSite=	Home page of PRIMO
ID=	Unique identifier that allows to know all files created during a given task (Associated files always have the same identifier)
Created=	Creation date of the certificate
Certificate=	Filename of the certificate associated with the report
TestCount=	Total number of tests in the certificate
[Backtrack]	Bactrack section
Count=	Total number of backtracked tests
Rejected=	List of the backtracked tests
[n] or [n (backtracked:m)]	Test section  n is the number of the test m is the number of times the test n was backtracked
Type=	Type of the test 0: Strong pseudoprime 1: N-1 2: N+1 3: Elliptic curve 4: Elliptic curve
Run=	Run on which the test was found (during Phase 1)
Gain=	Gain = BitSize(N) - BitSize(R) except for the last test where Gain = BitSize(N) The N value of a test is equal to the R value of the preceding test (or to the candidate for the first test)
D=	Discriminant used for the test
H=	Class number associated with the discriminant D
G=	Genus number associated with the discriminant D PRIMO has to factor a polynomial of which the degree is at most H/G
R$=	Backtracked tests only R (expressed to the base 16) is the value with which PRIMO failed to complete a test

---

Contents

PRIMO - Primality Proving. Copyright © 2007, Marcel Martin. All rights reserved.

By installing and/or using the software PRIMO (the "Software"), you (the "User") (either on behalf of yourself as an individual or on behalf of an entity as its authorized representative) agree to all of the terms of this end-user license agreement (the "Agreement") regarding your use of the Software and you also agree that this is the entire agreement between the author (the "Author") of the Software and you, which supersedes any prior agreement, whether written or oral, and all other communications between the Author and you relating to the subject matter of this Agreement.

GRANT OF LICENSE
Subject to the terms below, the Author hereby grants the User a non-exclusive, non-transferable license to install and to use the Software.

DISCLAIMER OF WARRANTY
The Software and its documentation are provided "as is" without warranty of any kind.
The Author makes no representations or warranties about the suitability of the Software, either express or implied, including but not limited to the implied warranties of merchantability, fitness for a particular purpose, or non-infringement.
If the User of this Software deems it unsuitable for any particular purpose, the User's sole remedy shall be to refrain from using it.
The Author shall not be liable for any damages suffered by the User as a result of using, modifying or distributing the Software, including direct, indirect, incidental, consequential or other damages, even if the Author has been advised of the possibility of such damages.

INTELLECTUAL PROPERTY
No title to the intellectual property in the Software is transferred to the User. Title, ownership, rights, and intellectual property rights in and to the Software shall remain to the Author.

TERMINATION
This Agreement shall terminate automatically if the User fails to comply with the limitations described in this Agreement. No notice shall be required from the Author to effectuate such termination. Upon termination, the User must uninstall and destroy all copies of the Software.

GOVERNING LAWS
This Agreement shall be governed by the laws of France.

PATENTS
If the Author is advised that the Software is infringing a patent, the Author shall forbid distribution and use of the Software in all countries where the patent is applicable. In this case, the User's sole remedy shall be to refrain from using the Software in such countries.

SEVERABILITY
In the event of invalidity of any provision of this Agreement, the Author and the User agree that such invalidity shall not affect the validity of the remaining portions of this Agreement.

RESERVATION OF RIGHTS
All rights not expressly granted in this Agreement are reserved by the Author.

June 21, 2007
Colombes, France

Contents