Solovay–Strassen primality test

The Solovay–Strassen primality test, developed by Robert M. Solovay and Volker Strassen in 1977, is a probabilistic primality test to determine if a number is composite or probably prime. The idea behind the test was discovered by M. M. Artjuhov in 1967[1] (see Theorem E in the paper). This test has been largely superseded by the Baillie–PSW primality test and the Miller–Rabin primality test, but has great historical importance in showing the practical feasibility of the RSA cryptosystem. The Solovay–Strassen test is essentially an Euler–Jacobi probable prime test.

Concepts

Euler proved[2] that for any odd prime number p and any integer a,

where is the Legendre symbol. The Jacobi symbol is a generalisation of the Legendre symbol to , where n can be any odd integer. The Jacobi symbol can be computed in time O((log n)²) using Jacobi's generalization of the law of quadratic reciprocity.

Given an odd number n one can contemplate whether or not the congruence

holds for various values of the "base" a, given that a is relatively prime to n. If n is prime then this congruence is true for all a. So if we pick values of a at random and test the congruence, then as soon as we find an a which doesn't fit the congruence we know that n is not prime (but this does not tell us a nontrivial factorization of n). This base a is called an Euler witness for n; it is a witness for the compositeness of n. The base a is called an Euler liar for n if the congruence is true while n is composite.

For every composite odd n, at least half of all bases

are (Euler) witnesses as the set of Euler liars is a proper subgroup of . For example, for , the set of Euler liars has order 8 and , and has order 48.

This contrasts with the Fermat primality test, for which the proportion of witnesses may be much smaller. Therefore, there are no (odd) composite n without many witnesses, unlike the case of Carmichael numbers for Fermat's test.

Example

Suppose we wish to determine if n = 221 is prime. We write (n−1)/2=110.

We randomly select an a (greater than 1 and smaller than n): 47. Using an efficient method for raising a number to a power (mod n) such as binary exponentiation, we compute:

  • a(n−1)/2 mod n  =  47110 mod 221  =  −1 mod 221
  • mod n  =  mod 221  =  −1 mod 221.

This gives that, either 221 is prime, or 47 is an Euler liar for 221. We try another random a, this time choosing a = 2:

  • a(n−1)/2 mod n  =  2110 mod 221  =  30 mod 221
  • mod n  =  mod 221  =  −1 mod 221.

Hence 2 is an Euler witness for the compositeness of 221, and 47 was in fact an Euler liar. Note that this tells us nothing about the prime factors of 221, which are actually 13 and 17.

Algorithm and running time

The algorithm can be written in pseudocode as follows:

inputs: n, a value to test for primality
        k, a parameter that determines the accuracy of the test
output: composite if n is composite, otherwise probably prime

repeat k times:
    choose a randomly in the range [2,n − 1]
    
    if x = 0 or  then 
        return composite
return probably prime

Using fast algorithms for modular exponentiation, the running time of this algorithm is O(k·log3 n), where k is the number of different values of a we test.

Accuracy of the test

It is possible for the algorithm to return an incorrect answer. If the input n is indeed prime, then the output will always correctly be probably prime. However, if the input n is composite then it is possible for the output to be incorrectly probably prime. The number n is then called an Euler–Jacobi pseudoprime.

When n is odd and composite, at least half of all a with gcd(a,n) = 1 are Euler witnesses. We can prove this as follows: let {a1, a2, ..., am} be the Euler liars and a an Euler witness. Then, for i = 1,2,...,m:

Because the following holds:

now we know that

This gives that each ai gives a number a·ai, which is also an Euler witness. So each Euler liar gives an Euler witness and so the number of Euler witnesses is larger or equal to the number of Euler liars. Therefore, when n is composite, at least half of all a with gcd(a,n) = 1 is an Euler witness.

Hence, the probability of failure is at most 2k (compare this with the probability of failure for the Miller–Rabin primality test, which is at most 4k).

For purposes of cryptography the more bases a we test, i.e. if we pick a sufficiently large value of k, the better the accuracy of test. Hence the chance of the algorithm failing in this way is so small that the (pseudo) prime is used in practice in cryptographic applications, but for applications for which it is important to have a prime, a test like ECPP or the Pocklington primality test[3] should be used which proves primality.

Average-case behaviour

The bound 1/2 on the error probability of a single round of the Solovay–Strassen test holds for any input n, but those numbers n for which the bound is (approximately) attained are extremely rare. On the average, the error probability of the algorithm is significantly smaller: it is less than

for k rounds of the test, applied to uniformly random nx.[4][5] The same bound also applies to the related problem of what is the conditional probability of n being composite for a random number nx which has been declared prime in k rounds of the test.

Complexity

The Solovay–Strassen algorithm shows that the decision problem COMPOSITE is in the complexity class RP.[6]

References

  1. ^ Artjuhov, M. M. (1966–1967), "Certain criteria for primality of numbers connected with the little Fermat theorem", Acta Arithmetica, 12: 355–364, MR 0213289
  2. ^ Euler's criterion
  3. ^ Pocklington test on Mathworld
  4. ^ P. Erdős; C. Pomerance (1986). "On the number of false witnesses for a composite number". Mathematics of Computation. 46 (173): 259–279. doi:10.2307/2008231. JSTOR 2008231.
  5. ^ I. Damgård; P. Landrock; C. Pomerance (1993). "Average case error estimates for the strong probable prime test". Mathematics of Computation. 61 (203): 177–194. doi:10.2307/2152945. JSTOR 2152945.
  6. ^ R. Motwani; P. Raghavan (1995). Randomized Algorithms. Cambridge University Press. pp. 417–423. ISBN 978-0-521-47465-8.

Further reading

  • Solovay, Robert M.; Strassen, Volker (1977). "A fast Monte-Carlo test for primality". SIAM Journal on Computing. 6 (1): 84–85. doi:10.1137/0206006. See also Solovay, Robert M.; Strassen, Volker (1978). "Erratum: A fast Monte-Carlo test for primality". SIAM Journal on Computing. 7 (1): 118. doi:10.1137/0207009.
  • Dietzfelbinger, Martin (2004-06-29). "Primality Testing in Polynomial Time, From Randomized Algorithms to "PRIMES Is in P"". Lecture Notes in Computer Science. Vol. 3000. Springer. ISBN 978-3-540-40344-9.
  • Solovay-Strassen Implementation of the Solovay–Strassen primality test in Maple

Read other articles:

Universitario (CUBA)Nama penuhClub Universitario de Buenos AiresUniUnión de Rugby de Buenos AiresJulukanCUBADidirikan11 Mei 1918; 105 tahun lalu (1918-05-11)LetakBuenos Aires, ArgentinaLapanganVilla de Mayo, Buenos Aires RayaKetuaMarcelo Perri[1]PelatihJuan José Villar Tomás CóppolaLigaTorneo de la URBA Grupo I20168° of Top 14[2] Baju ke-1 Baju ke-2 InternasionalSitus web resmiwww.cuba.org.ar Templat:Club Universitario de Buenos Aires sections Club Universitario de B...

 

 

Sci-Fi HARRYBerkas:Sci-Fi Harry.jpgSampul Manga (vol.1)サイファイハリーGenreDrama, Horror MangaPengarangGeorge IidaIlustratorAsami TohjohPenerbitTakeshoboTerbitJuli 1995 – November 1995Volume2 AnimeStudioStudio A.P.P.PTayang 5 Oktober 2000 – 23 Maret 2001 MangaPengarangGeorge IidaIlustratorAsami TohjohPenerbitKadokawaTerbit2000 – sekarangVolume2  Portal anime dan manga Sci-Fi HARRY (サイファイハリーcode: ja is deprecated , Sai fai harī) Adalah seri manga 1995 o...

 

 

Shinto shrine in Japan Hikawa ShrineReligionAffiliationShintoLocationLocation6-10-12, Akasaka, Minato, Tokyo 107-0052Shown within JapanGeographic coordinates35°40′5.57″N 139°44′8″E / 35.6682139°N 139.73556°E / 35.6682139; 139.73556ArchitectureFounderTokugawa YoshimuneDate established1730Websitewww.akasakahikawa.or.jp Glossary of Shinto Hikawa Shrine (氷川神社, Hikawa-jinja) is a Shinto shrine in Akasaka, Tokyo, Japan. In Tokyo, it is the best known of t...

American college football season 2021 Auburn Tigers footballBirmingham Bowl, L 13–17 vs. HoustonConferenceSoutheastern ConferenceDivisionWestern DivisionRecord6–7 (3–5 SEC)Head coachBryan Harsin (1st season)Offensive coordinatorMike Bobo (1st season)Offensive schemesinglebackDefensive coordinatorDerek Mason (1st season)Base defense3–4Home stadiumJordan–Hare StadiumSeasons← 20202022 → 2021 Southeastern Conference football standings ...

 

 

Grotte, Agrigento commune di Italia Grotte (it) Tempat Negara berdaulatItaliaRegion otonom dengan status khususSiciliaProvinsi di ItaliaProvinsi Agrigento NegaraItalia Ibu kotaGrotte PendudukTotal5.209  (2023 )GeografiLuas wilayah23,98 km² [convert: unit tak dikenal]Ketinggian516 m Berbatasan denganAragona Comitini Milena (en) Racalmuto Campofranco (en) Favara, Agrigento SejarahSanto pelindungSaint Veneranda (en) Informasi tambahanKode pos92020 Zona waktuUTC+1 UTC+2 Kode telepon092...

 

 

Phyllis AllenAllen bersama Mack Swain (berdiri), Mabel Normand dan Charlie Chaplin di Getting Acquainted (1914)Lahir(1861-11-25)25 November 1861Pulau Staten, New York, U A.S.Meninggal26 Maret 1938(1938-03-26) (umur 76)Los Angeles, California, A.S.PekerjaanAktris, komedian, vaudevillianTahun aktif1913–1923 Phyllis Allen (25 November 1861 – 26 Maret 1938) adalah seorang komedian dan aktris film bisu asal Amerika Serikat. Dia bekerja dengan Charles Chaplin, Mabel Nor...

Letter Ṛ in Indic scripts For the Indic consonant R, see Ra (Indic). For the vowel-like letter often referred to as a vocalic R̄, see Ṝ (Indic). ṚExample glyphsBengali–AssameseTibetanཨྲྀMalayalamഋSinhalaඍAshoka BrahmiDevanagari CognatesHebrewרGreekΡLatinRCyrillicРPropertiesPhonemic representation/ɻ̩/IAST transliterationṛ ṚISCII code pointDF (223) This article contains uncommon Unicode characters. Without proper rendering support, you may see question m...

 

 

Hungarian football club This article does not cite any sources. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: FC Veszprém – news · newspapers · books · scholar · JSTOR (February 2010) (Learn how and when to remove this template message) Football clubVeszprém FCFull nameVeszprémi Football ClubFounded7 January 1912; 112 years ago (7 January 1912)Gro...

 

 

Fun guoSebuah baki kukus dengan tiga fun guoNama lainChaozhou fun guo, fun quor, fun gor, fen guo, dumpling Chiu Chow, dumpling Teochew, hung gue, fun korSajianYum chaTempat asalChaoshan, Guangdong, Tiongkok SelatanDibuat olehSuku TeochewSunting kotak info • L • BBantuan penggunaan templat ini  Media: Fun guo Fun guo Hanzi tradisional: 潮州粉粿 Alih aksara Mandarin - Hanyu Pinyin: Cháozhōu fěnguǒ Min Nan - Romanisasi POJ: Tiô-chiu-hún-kué, Tiô-chiu-hún-ké ...

Association football club in England This article is about the English men's football club. For the city in which the football club is situated, see Liverpool. For the affiliated women's football club, see Liverpool F.C. Women. For the Uruguayan men's football club, see Liverpool F.C. (Montevideo). For other uses, see Liverpool F.C. (disambiguation). Football clubLiverpoolFull nameLiverpool Football ClubNickname(s)The RedsFounded3 June 1892; 131 years ago (1892-06-03)[1&...

 

 

12th century Telugu, Kannada and Sanskrit writer Palkuriki Somanatha was one of the most noted Telugu language writers of the 12th or 13th century. He was also an accomplished writer in the Kannada and Sanskrit languages and penned several classics in those languages.[1] He was a Veerashaiva a follower of the 12th century social reformer Basava and his writings were primarily intended to propagate this faith.[1] He was a well acclaimed Shaiva poet.[2] The trio of Nanne...

 

 

Carl Perkins Nazionalità Stati Uniti GenereRock and rollRockabillyCountryGospel Periodo di attività musicale1946 – 1998 Strumentovoce, chitarra EtichettaSun Records, Columbia Records, Mercury Modifica dati su Wikidata · Manuale 1 volta vincitore ai Grammy awards Carl Lee Perkins (Tiptonville, 9 aprile 1932 – Jackson, 19 gennaio 1998) è stato un cantante, compositore e chitarrista statunitense. Pioniere dei generi rockabilly e rock'n'roll, Carl Perkins è s...

Rondacomune Ronda – Veduta LocalizzazioneStato Spagna Comunità autonoma Andalusia Provincia Malaga TerritorioCoordinate36°44′14″N 5°09′53″W / 36.737222°N 5.164722°W36.737222; -5.164722 (Ronda)Coordinate: 36°44′14″N 5°09′53″W / 36.737222°N 5.164722°W36.737222; -5.164722 (Ronda) Altitudine723 m s.l.m. Superficie481,31 km² Abitanti36 827 (2009) Densità76,51 ab./km² Comuni confinantiAlcalá del Val...

 

 

此條目可参照英語維基百科相應條目来扩充。 (2021年5月6日)若您熟悉来源语言和主题,请协助参考外语维基百科扩充条目。请勿直接提交机械翻译,也不要翻译不可靠、低品质内容。依版权协议,译文需在编辑摘要注明来源,或于讨论页顶部标记{{Translated page}}标签。 约翰斯顿环礁Kalama Atoll 美國本土外小島嶼 Johnston Atoll 旗幟颂歌:《星條旗》The Star-Spangled Banner約翰斯頓環礁�...

 

 

Северный морской котик Самец Научная классификация Домен:ЭукариотыЦарство:ЖивотныеПодцарство:ЭуметазоиБез ранга:Двусторонне-симметричныеБез ранга:ВторичноротыеТип:ХордовыеПодтип:ПозвоночныеИнфратип:ЧелюстноротыеНадкласс:ЧетвероногиеКлада:АмниотыКлада:Синапси...

此條目可能包含不适用或被曲解的引用资料,部分内容的准确性无法被证實。 (2023年1月5日)请协助校核其中的错误以改善这篇条目。详情请参见条目的讨论页。 各国相关 主題列表 索引 国内生产总值 石油储量 国防预算 武装部队(军事) 官方语言 人口統計 人口密度 生育率 出生率 死亡率 自杀率 谋杀率 失业率 储蓄率 识字率 出口额 进口额 煤产量 发电量 监禁率 死刑 国债 ...

 

 

President of The Church of Jesus Christ of Latter-day Saints This article is about the president of The Church of Jesus Christ of Latter-day Saints. For others of the same name, see George Albert Smith (disambiguation). George Albert Smith8th President of the Church of Jesus Christ of Latter-day SaintsMay 21, 1945 (1945-05-21) – April 4, 1951 (1951-04-04)PredecessorHeber J. GrantSuccessorDavid O. McKay President of the Quorum of the Twelve Apostle...

 

 

Calendar year Millennium: 2nd millennium Centuries: 11th century 12th century 13th century Decades: 1100s 1110s 1120s 1130s 1140s Years: 1122 1123 1124 1125 1126 1127 1128 1125 by topic Leaders Political entities State leaders Religious leaders Birth and death categories Births – Deaths Establishments and disestablishments categories Establishments – Disestablishments Art and literature 1125 in poetry vte 1125 in various calendarsGregorian calendar1125MCXXVAb urbe con...

American singer (1939–1984) For the song, see Marvin Gaye (song). Marvin Gay redirects here. For his father, see Marvin Gay Sr. Marvin GayeGaye in 1973BornMarvin Pentz Gay Jr.(1939-04-02)April 2, 1939Washington, D.C., U.S.DiedApril 1, 1984(1984-04-01) (aged 44)Los Angeles, California, U.S.Cause of deathGunshot woundsOccupationsSingersongwritermusicianrecord producerYears active1957–1984Spouse Anna Gordy ​ ​(m. 1963; div. 1977)​...

 

 

For other Pennsylvania townships with similar names, see Foster Township, Pennsylvania (disambiguation). Township in Pennsylvania, United StatesFoster Township, Luzerne County, PennsylvaniaTownshipEckley Miners' Village in Foster TownshipMap of Luzerne County highlighting Foster TownshipMap of Pennsylvania highlighting Luzerne CountyCountryUnited StatesStatePennsylvaniaCountyLuzerneSettled1824Incorporated1855Area[1] • Total45.14 sq mi (116.92 km2) •&#...