Primo Help Contents

PRIMO - Primality Proving

Contents

- Manual

- Overview
- Getting started
- Button bar
- Task Report page
- Certification page
- Verification page
- What is a primality certificate?
- How to resume a certification?
- Internal Errors

- Files

- Input (Candidate)
- OutPut (Certificate)
- Task Report
- Certification Report

- Miscellaneous

- End-User License

Overview

> What is PRIMO ?

> PRIMO is a primality proving program based on the ECPP algorithm: Elliptic Curve Primality Proving. Given positive odd integers, PRIMO tests whether these integers are prime, and if they are it produces primality certificates.
> PRIMO is suitable for the checking of crypto-primes and to prove whether they are actually prime... or not.

> Latest Release

> To check whether you have the most recent version of PRIMO, please, visit the PRIMO Home page

> Contact

> Send any comment, suggestion, bug report, whatever to primo@ellipsa.eu

> Contents

Getting Started

> 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

Button Bar

> 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

Task Report Page

> 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

Certification Page

> 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

Verification Page

> 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

Certificate

> 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

Resuming

> 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

Internal Error

> 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

Input File

> 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

Output File

> 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=09/03/2010 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

Task Report File

> 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=09/03/2010 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

Report File

> 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=09/03/2010 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

License

> PRIMO - Primality Proving. Copyright © 2010, 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.

> Contents

Copyright © 2010, Marcel Martin
http://www.ellipsa.eu/index.html