Тест Пепина

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Тест Пепина — тест простоты для чисел Ферма. Тест назван в честь французского математика Феофила Пепина.

Описание[править | править вики-текст]

Псевдокод

b\,\leftarrow\, 3
ОТ i=1 ДО 2^n-1 ВЫП b\,\leftarrow\, b^2\bmod{F_n}
ЕСЛИ b\equiv -1\pmod{F_n} ТО
ВОЗВРАТ «F_n — простое»
ИНАЧЕ
ВОЗВРАТ «F_n — составное»

Тест Пепина состоит в возведении числа 3 в степень (F_n - 1)/2 = 2^{2^n-1} (серией из 2^n-1 последовательных возведений в квадрат) по модулю F_n. Если результат сравним по модулю F_n с −1, то F_n является простым, а в противном случае — составным.

Приведем формулировку в виде теоремы:

При n ≥ 1 число Ферма F_n = 2^{2^n}+1 является простым тогда и только тогда, когда 3^{(F_n-1)/2}\equiv-1\pmod{F_n}.

Доказательство[править | править вики-текст]

Предположим, что сравнение верно. Тогда условие теоремы Люка выполняется при n = F_n, а = 3, следовательно, F_n является простым числом. Обратно, пусть F_n — простое число. Так как 2^n — четное число, то 2^{2^n}\equiv1\pmod{3}, следовательно, F_n\equiv2\pmod{3}. Но F_n\equiv1\pmod{4}, поэтому символ Лежандра \left(\frac3{F_n}\right) равен −1. Следовательно, 3 не является квадратичным вычетом по модулю F_n. Необходимое сравнение следует из критерия Эйлера.

Замечания[править | править вики-текст]

Тест Пепина является частным случаем теста Люка.

Число 3 в тесте Пепина может быть заменено на 5, 6, 7 или 10 (последовательность A129802 в OEIS), которые также являются первообразными корнями по модулю каждого простого числа Ферма.

Известно, что Пепин привел критерий с числом 5 вместо числа 3 (и при k ≥ 2). Прот и Люка отметили, что можно также использовать число 3.

Вычислительная сложность[править | править вики-текст]

Так как тест Пепина требует 2^n-1 возведений в квадрат по модулю F_n, то он выполняется за полиномиальное время от длины числа F_n. Однако, если на вход подается лишь число n, то тест Пепина выполняется за сверх-экспоненциальное время от длины входа (\log n).

История тестов Пепина[править | править вики-текст]

Из-за большой редкости чисел Ферма, тест Пепина был выполнен всего 8 раз (на числах Ферма, чья простота еще не была доказана или опровергнута). [1][2][3]Майер, Пападопулос и Крэндалл выдвинули предположение о том, что в действительности, должно пройти несколько десятилетий, прежде чем технологии позволят выполнить новые тесты Пепина, поскольку размеры еще неисследованных чисел Ферма очень велики.[4] На момент 2012 года наименьшим непроверенным числом Ферма является F_{33}, которое содержит 2,585,827,973 десятичных цифр.

Год Исследователи Числа Ферма Результаты теста Пепина Делитель найден в последствии?
1905 Джеймс С. Морхед и Альфред Вестерн F_{7} составное Да (1970)
1909 Джеймс С. Морхед и Альфред Вестерн F_{8} составное Да (1980)
1952 Рафаэль М. Робинсон F_{10} составное Да (1953)
1960 Г. А. Паксон F_{13} составное Да (1974)
1961 Джон Селфридж и Александр Гурвиц F_{14} составное Да (2010)
1987 Дункан Бьюэл и Джеффри Янг[5] F_{20} составное Нет
1993 Крэндалл, Дж. Диньяс, С. Норри и Джеффри Янг[6] F_{22} составное Да (2010)
1999 Эрнст В. Майер, Джейсон С. Пападопулос и Крэндалл F_{24} составное Нет

Примеры реализаций алгоритма[править | править вики-текст]

Пример реализации на языке Python:

base = 3
 
while True:
    try:
        character = int(input('Input a characteristic of the Fermat number, please: '))
        break
    except ValueError:
        print("The characteristic should be a number. Try again, please.")
 
power = 2 ** character - 1 
fermat_number = 2 ** (2 ** character) + 1
 
for i in range(1, power+1):
    base = (base ** 2) % fermat_number
 
if base == (fermat_number - 1):
    print ('The number F' + str(character) + ' is simple')
else:
    print ('The number F' + str(character) + ' is complex')
 
print('F' + str(character) + ' = ' + str(fermat_number))

Пример работы программы:

Input a characteristic of the Fermat number, please: 15
The number F15 is complex
F15 = 1415461031044954789001553027744951601348130711472388167234385748272366634240845253596025356476648415075475872961656126492389808579544737848881938296250873191743927793544913011050162651277957029846960211783242933521207545413484969856851851141288515163201482995389055097460622098635675003353929224278582935664416262572773308153277514346480313371988612629481483562438178928958867777850072198316174841251955590996672018645093640850803679630220367201383844866791449284737518262813123083439037243678440420897139923778278952770312318778329004894547065489077596835396017153603170050371302014762443872701111379554484309718662306883776010475348441493600491943479041271992920195331983064930106164727241438940877685164658948654886171641124473975626241632750150126655369981021293570066042305482486040883165635862835728637046058352403756085745691239473897891999085976345203704659967157427239535836507133656908815246080139195569461072006301590372954830738644391138016065344131131207604264053897440828904662047183234377547427287691941741535946510882990904477863185473798528388060457568927943633923928872681927502029572963130840854853739937076881035646179383055483433876051402037614424748902969018159186519811051545367967103767182819709135479019131683309330797374408197339831527239040715908112213095126770717606001288898889370710896248862361503869205214536908258196921765593065325392836332142594411134603475509366028145690306350601859295261296263331018682276317567749534571058772235567679556920240789109070521253987131031263902293034744367356932509952188828475362311316445284228640489421809263738423630931243024914587863928134719186104164660605356001591962778646378295413659770782646979236289062616442418071571039282551289348848274522893059561717860194034698241804887531275078109603637160495907579995366419636417028927573391670580796818526074226095014375189438579216071677540766085605604106123036669667434677723472675564458991671268414100801031453917736665947284956674884035306621286465183798693852599803324619865181856244422079233687294508536408521087418873908498202710597080474480249818858011490930518512713798803629101638716278578874145214429026186276602289012484526830076647356828764878327726719816428678904207944456894393185983090347045176886732326253912297649524439880403701430566761380359925558522718201954287517587367247510777678934664472548647787048306330770862370015525858005479756471499227244901142805749769564184753211967223226212964165678856604892416984915097422960534122333453876981279243565766391796311605149222628328255333061543877525846029404507128890053189442527544665141513571136187126874914601669750392486100507568442046831780631032540574077944274454228087639241736818505163759910365131990632947462993204585218122431992323864244947394390438656356424037471932484452186545692102503479070599953823165194211019696760575264426802848303031804305733532228050180286034175168918827460626042268658295140706915047189049492578996650494005882337071150004868956193406593184838633694068409823903437144417376039174235011053228846851424217955172902918651003610984108402650929359396305634313047088725113039076811940090109855578285937829164213576612822210347957745947331047482525346602542653176899809278808232796557531832150249769253600667902268029661700149632868541956266119528042486534014778779846981761033155007262730162675954520221887384710387051721829271917592295057169589539706361671082094809405871790468623234895914796464390019259167513771864832869036015645542195008456098615038348028400803005801944957156282746379539470250603755465358786281476086044567893715130635914946085361612372742732638037372287633897118303250036355897758209569010246051563429109255864938245524550200580218274314809738075022775651220374105227215906205292751918667060475328593225367793061070422108733800983855507591806413460964585595316359971179284283604731468668545484761381747591639736453419896449323486397030776397761202590467637505473390222249456724093238682557762781839530938233751281999608711356147835655195236666056355678841889862284014674059052995170220711404445012766642203314592371712594877968343265210232798135023299117318191770365123807086704381809759602260151612996896994294186084475619138121455294389585874237791634701296124550179672059485838256445846530599137662480841344376503989244633345016070887198120421435575726237189312161818021548006389501182393441712142044953072264016676799011624620312246468554654371544717355227740157629086739710675845209992133342035144038961065892653392182875622932670067798433934891709519877850794219491447988160171932331006495620280094149464379450153085406225081471879585894087916092141623752345112751067703166403681162331920291740847388957632311053342426152947324011627922225878539935022974616062774839110489080094174972841068102006645677499293769091362853719300958775222088670909723895414866464400756314470281962034276531512544009726174649399937581739718117982417360985958259468485436586733686659771030677664677905401522360041892481951454135360540917411098412286723830672712910603386748136348878056545746112142111116659985782398275627122449414307140749404884060753863706024281031485538666133332835597817514616331728118982180628823657668668099621799842011158020767772792912298768785614574416019320546196793486018677884550715870608004988829978148966980770136884353226949853654541655837029498017031085943660440466076019479435181045436897845351048788440102268677798257134774081674357195358847761226603653040273985441982221318087815835107317571211841215825606453348521097936413520295998260751040778703740366309871999114717441069182825782996299411623087415008910941303284182131584799816210728034255555687956785287887098941927737599159824398527573423117728252839768919145018117995597946282264946523741691180858441194373387098969530126834014923656627849129062189145572870212225909464530919531634090206371146321663797279805760028495288084848179380053931435604182517516600823936737919915974103591167638898871754018470172589234989397051893028574365288890303780239194622538215532212735555299397542845350629361560347195459286729561168235383428930828378887678197590624110372267338756668414899526138480866747114831414687579691636020586013635675559033488649721062244142787960404056961306176022981242840984825421797150393909713884990708008654327558025619074213270714252431515171638994505720144347502185848528129000055629703422695425047209518177577128511315492059613722366724615343968357332924191178041956753132941596322101250417068813977303498033940613791099720174786773844696734034010269139553878212387108508158622839733593634918975616613368243882808391509244806809337882965338701545504691589517650472239580754189547649790038026506707709763098148746524031013800531890876858227360501676161874661946431647929572555992967298553471152693471452480119897608173336753260124452510815333416409357029633265172614203663326409976153102467083379129588112837280711111346490898947808402062401228963194162711657422998429263579276515414000979053740662733816632981508535128518440258006782392288860903823207436820793041881907093791874917635829854808150640894907127600430185202301457398493533111918994100853753771956293430162566011361163168953462188010231819000213669780447856871248564377584509085888797883747538309181810700615032225563091016689474780253412571338625581817921061549352557588323659562675650563535186144754433556539747098322643609542486120512917463706713059064230762924353617972053492527119192658171851345957700772571841998176036269399889012480745075924980479390349332734102774400008120073461540540571051506971003904623484344762005126345905465893817895377928139596549936720100490013375956605889200767596688065961076003472005585890222594655010430123127351665316862663484785966446263740624564875351640780923703006868107440790271682936043304873579648989978571754898840789184480129570446991029504758616393106487523321312507454036808667210073602144290050619610614738139543285649346986393213102456863793665512533655931941790537619020604730601443181250662019687491711547360597117856977240817110039737153355212454745907787131179578656470567535050192702347739653312290522505871612897990429961857550031033665725647987982751868407294730437319505335782425290324427994308374960806684435416445907817107168298342945182985594111281499472495749501642418042734681158560450241309279063816746067016274795461832774699007774423895748677615395848493765672271957278664546343161609126810028254214659633625223934508931691728584028342356669332635458079957147833789501696835781748234884919093574276330354577841975249603899105407104895787598263630679206627796433754045597409176502438867600537016879169914474754840024311922169647388379952802523847080102439285112565751677726373201688403254466789070713575214256192452449029110040537994627424532403620179880056518721219108771374073638118719073211367295514376708596537294204544099903590754371656178656960170217675832153268164591674004500239073743502648099105624548587493544825479270589742494495181223722329693345468639306990523118995640567042531369577131113159027381808071346991604513906450398219426300899204662435492578485666553974492723173859777485412927016068341515517437115137050372750279278548332799193799400154166442801427310076537020119936073495221974791939759846168942055397357348278178050441024490005893818256958665388971201322931680573846084525016332224646866617490832496084991690171583029352609836490908113464668343829985351590552945284372573978295485097950893072423518605982085487154470155025269025854044646496572448495225343096261896378931482883286657508859228868487844184479087538453974144187004884366561256723404772190847586008543961349071131191708943295337664384184532774661503245910257451923515607711559705478132556040197663414911885143697985464807309297002910250505302287769412337441199360424519160716552890882816796378296881641827981453035207233752063518782778493743827708109913493162932182427627261046280168269958077541122668104633712377857

Примечания[править | править вики-текст]

  1. Conjecture 4. Fermat primes are finite — Pepin tests story, according to Leonid Durman(англ.)
  2. Wilfrid Keller: Fermat factoring status(англ.)
  3. R. M. Robinson (1954): Mersenne and Fermat numbers(англ.)
  4. Richard E. Crandall, Ernst W. Mayer & Jason S. Papadopoulos, The twenty-fourth Fermat number is composite (2003)(англ.)
  5. Jeff Young & Duncan A. Buell (1988): The twentieth Fermat number is composite, 261—263.(англ.)
  6. R. Crandall, J. Doenias, C. Norrie, and J. Young (1995): The twenty-second Fermat number is composite, 863—868(англ.)

Литература[править | править вики-текст]

  • P. Pépin, Sur la formule 2^{2^n}+1, Comptes Rendus Acad. Sci. Paris 85 (1877), pp. 329—333.
  • Крэндалл Р., Померанс К. — Простые числа(2011), стр. 198—200.