Please use this identifier to cite or link to this item: https://scholarbank.nus.edu.sg/handle/10635/180495
Title: JACOBI SUM PRIMALITY TEST
Authors: GOH GEOK YEN
Issue Date: 1998
Citation: GOH GEOK YEN (1998). JACOBI SUM PRIMALITY TEST. ScholarBank@NUS Repository.
Abstract: Many methods have already been developed to test the primality of a number. For instance, we have probabilistic methods like the Rabin-Miller test, methods involving special forms of N such that N - 1, N + 1 has a factorisation and finally almost deterministic methods (in the sense that if the number passed the test, then it is definitely prime) like the Jacobi sum primality test which we are going to discuss in this thesis. We observe that many primality testing algorithms are based on the trivial fact that a number N > l is prime if and only if every divisor r of N is a power of N. In the actual primality tests, one however checks the above fact for images of r and N in certain groups. There are basically three stages in such primality testing algorithms based on the above fact .. The first stage consists of selecting a suitable auxiliary group G. Further, it is supposed that there is a natural map ? from the set of divisors of N to G with the property ?(rr') = ?(r)?(r') if rr' I N. In the second stage, one attempts to show that ?(r) is a power of ?(N) for every r I N. The second stage consists of subjecting N to a collection of pseudo primality tests with the properties that if N is prime, then it passes the tests and conversely if N passes the tests, then ?(r) is in the subgroup of G generated by ?(N). The third stage involves the use of the information from the first two stages to complete the primality test. In our Jacobi sum primality test, we shall choose an auxiliary number s = c(t) (section 1.3) and take the group G to be C* and the map ? to be a character C; also for several small primes, we shall take G to be (Z/pZ)*, a ? Z and the map ? to be ?(r) = rp-1. The main result. is stated in chapter 1, section 3 and subsequent sections are devoted to determine algorithmic ways of checking the required conditions stated in the main result. We have, implemented the algorithm for numbers up to 213 decimal digits using the auxiliary number t = 55440 and later extend it to numbers up to 474 digits using t = 720720. Two multiprecision packages, LIP and the GNU package, are tried and it is found that the program runs faster under the GNU package. Hence, only the GNU version of the source code is presented in this thesis. Pomerance and Odlyzko [2] have shown that the running time of the Jacobi sum algorithm is O(lnN)C In In InN for some constant C which is almost polynomial time. This shows that it works quite well in practice. We have tabulated the running times of some probabilistic numbers (subject to our algorithm) in the implementation section. Finally, we note that one can combine this test with other tests like the LncasLelmwr test. To achieve higher efficiency. We also note that in onr program, we have assumed the number we are testing has passed a number of probabilistic tests. We have not incorporated these tests in our program but have used those programmed by A.K. Lenstra in LIP.
URI: https://scholarbank.nus.edu.sg/handle/10635/180495
Appears in Collections:Master's Theses (Restricted)

Show full item record
Files in This Item:
File Description SizeFormatAccess SettingsVersion 
B21050235.PDF2.17 MBAdobe PDF

RESTRICTED

NoneLog In

Google ScholarTM

Check


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.