mersenneforum.org Cheap Cyclic Fermat's Tests
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2023-02-14, 18:52 #1 a1call     "Rashid Naimi" Oct 2015 Remote to Here/There 22·5·7·17 Posts Cheap Cyclic Fermat's Tests According to Fermat's PRP test if N | a^(N-1)-1 Then N is a probable prime to base a. This can be a computationally expensive test if N is a very large integer. Now as an example and (ignoring the fact that Mersenne numbers are always PRP to base 2): 7 | 2^(7-1)-1 so it is a PRP to base 2. A shortcut would be that since 7 | 2^(3)-1 and since 3 | ( 7-1) it follows that 7 | 2^(7-1)-1 Or more generally 7 | 2^(N-1)-1 for all integers N where 3 | (N-1) This can be used to perform very cheap tests for very large integers N where if N | a^(x)-1 && x | (N-1) Then N is PRP to base a. This can be used to construct very large integers N that will pass the test for very small integers x. Unfortunately these constructed integers generally end up being Pseudoprimes to base a and the test has little practical use. However, it is conceivable that some general candidates will yield a not so small x partway before the full exponentiation is performed, indicating if the candidate is a PRP or not. I would appreciate your thoughts and thank you for your time. Last fiddled with by a1call on 2023-02-14 at 19:16
 2023-02-14, 22:06 #2 Happy5214     "Alexander" Nov 2008 The Alamo City 22·5·72 Posts The Solovay–Strassen primality test yields a result with one fewer iteration (when squaring) (half the N) of a Fermat test, if you're willing to check for a Jacobi symbol (which runs in logarithmic time, so it's relatively cheap compared to the main test). A weaker test involves a simple equality check for 1 or N - 1. The Solovay–Strassen test sits between the Fermat test and the Miller–Rabin test in terms of strength. Edit: Sorry, I had a different post in mind before I remembered my logarithms. And you did say "not so small". Last fiddled with by Happy5214 on 2023-02-14 at 22:11 Reason: Correction
2023-02-15, 14:04   #3
a1call

"Rashid Naimi"
Oct 2015
Remote to Here/There

238010 Posts

Quote:
 Originally Posted by Happy5214 The Solovay–Strassen primality test yields a result with one fewer iteration (when squaring) (half the N) of a Fermat test, if you're willing to check for a Jacobi symbol (which runs in logarithmic time, so it's relatively cheap compared to the main test). A weaker test involves a simple equality check for 1 or N - 1. The Solovay–Strassen test sits between the Fermat test and the Miller–Rabin test in terms of strength. Edit: Sorry, I had a different post in mind before I remembered my logarithms. And you did say "not so small".
Thank you for the link Happy5214,
However there are more than one subject there which are above my comprehension.

To clarify the concept I was referring to, here is a numeric example:

Code:
PRP22067 = 14081760257558730022545694985196062520493780635673898439426688430440965675893551690213884631042989421621898326633118368644188602409144124617319329324248968764792434142541280853494632202391967283366586824282513133712820015940364412849671771270204883586830761568659016331622397304133354365581981567716526076973712803217866397676020480235592542918136524343781021482665351592051541200684540430069483679614591643775527384380955219374420339766520110185178556989236953999725689826320432602075018065320793472649042557739178061091980016111354783934556539617148150952340536657776229921026250428234486396280099338986396666256248730051716141174760105195232917791043856310044910661949610100394791214455703577996444119401472984634881305379311740224678093886859469808162477254048080680996557160333833771652863480724103469843919778684837488270655102076236439476199832424194131066140587760689282194484067550953202950452950973883006399798695526320788922822803447908634827890454422311211862398625642413092783228047859335339965956732434900255391469391614246015174653465241836034100689886229611255174639837947322406632536641697795182274773021609220397383693614245936580826403125987674572539410721930334794879938689322202865160890652029897755424709961397535660280882463183065258480350819924022497396752230213200157526717620913746691434400673668084829809467836982339386561371394485899257219941470320784429256326061630799620522613354993235125162174766756704744900249908145550460972382479275017426051273722153157567151888063590247018589005091155742125722478241545102066982136409439719534033500903774999376830089639822089548759722257834099830673894110820550702813846633070547758010729638838889402145896789725281379573278762176017933541594180767443892395235799701657913623966346954044825824636920987970928011430590101569367489495529052909571576970901037870766781521473186515126658198397158823263684192392027121209547499980044176753337352021246944349041483232615162651438976761066250617010804895353841336931912023777182633477864382886604000582100999551500921343344496696927371197465222372330297940926139795776167035562165241189640848926727256649042530161553807062735665576763458611277642071462240921009886604244029871045601003061615030429163530592899753082834331361878946733125232794568380992433301754357446683617817756949061916048039817819968064387278471830583509337314077557563226602388714491376852651272867201032419444293101859687359978573573385260971267110267380716423896203616928435524425073534367683804133295726573499530359346062659908022382261484648490930928332605938197392982546604361914393603531889012786099986625501663569447363665975581252661587952594093166953375870200214622304301976628590950562412557609374458338605937117367953873900682250792027303635488694403444270980951296954131504526520831998570615824636440562621028423590093115998465792281375725186644362001312734613407431732039560143500609538659898424358552677194902590669123535684934779622387136349438007695931898906624105064023498485279035961237263721775696409559667702032221458544537351461997507819671612197087564090962487484561963518003566799630410285605870154553620408033131394604977138363872930511905924709023253161173361869860896809605542371542673256863950436999800620635198996310777828220687049507346504179885384347124623216785284437297027416665894504052411351138053585771839398862759051048859071464353655869050321681487878908874222761710839713581834333029662287074811457957645825596522296582080519950893937525644720272870060553163263488133890651979548255893700795871770568591679505233160896175119675403470245688984409107739095591131331294482238215982166212597556550136875684814645016088024553298069979537171026956014100497009339010162813775333597375819957284524134385859085651269842515829153804556196284641543110704264690490287636460145235427360337455681170839756718215839847736008345655653160425975007965655792495080800361754289325136737762394772454966381014209823434893920924628503129510028930949303162051407426799730398035735181759524308023089191473049056940257179881684533752552006286044279475026204548623345668819297373202974861547755100785274192498565768379541435405559755617208621132235892747890058193035288220307186242093418854685225586727302368799512597840300359738743595266924317407050317862414409145497020767048041608725759110982101232628615571387910392424782140763307890815094248714034356559699260292035152714044284673679757608442328000340194761527795033084013912539198997044225660630235487086190119276070823114352091051170635568797731795770328528177282518810918942017909142956490953098774629963101863128203699241399984611212327086212580339845185951437879365823104681610981509039041026055184470955913787490932383901383559549058627879003503161420987977638215407468052792394073371401059772665431068396760025998376520730261740591618111869715794924137436104124650527790492717880726465144455731897778294847332641463340910960612007474245353495767516207019395274630654924357010903159779301158970485890852412860595787909409197445708891083273531992884553997631930185960893468016664359480574736984379540431244382238510956392077844556590055060406271776991229526876750918193229241115891458261932004973867586076884250341483637214629595528511353973738990762715951680186767259540775310890776326080409029180533095042816480099561336683272869820672172448769803508749641955571204044803547363157580553142844666217311160306858786730514980432811940620487798344350073549893431255711685353962547741207578584193703940856550247449767616688052501446642843231347725292530869874519662195199084477899470842627450751170679113060903227591037838433376835440705962195568080462489116135699138837480290382537508545493025164310407014671079122330128008601446635336497914310051450390443783393802888447507106066161989156353886456606035329793509614090598533355836706677801471303890190798996453380280463283627145592714141590404590945239225615518543962381311959263057794047008278178638434956048987084543824166151685522826768866001961531265275465394703878824181950693304081949102682302398613709449412685086059764581593257643236509075811029809788222058390183882148898733509834768453005487412912163214375165847676509602573769384867529964864208564697445237310743732750593660305613677640838521467695948608257009502851250465730165160886369194613558185792076011280573430431331477657620609461087598235854223054245789403011994964157392559862674196301121801091461520297341836658719430509475388552464730488383850178515762271785551931097124768906322411736942342021335401129163710825039196770821401904912310443975216988144263934153898197736691819352612829532176360827629983683881315207611186289460501083545960278577948109731351526689129774962054199943495372291656417660170045519109405007392442750800398900131556175281753127036849550045236339074092482010572276243117452843608501802091998056066725224838098968844789347378060960896212400145220317322160831046490762435981164806808099925733650535438170560119806475581528403872038985040535944652630825068615041469764782942614270915468797635543999868688746043035769554981413585993631029495972055426475808220256068825897504909486244235531101352744833507165396293245925290287596429252136370676097732435906025150848427681894697402122513236669048446029077477009008905561089760206482319198071515854727994642296564715545584763213453614434269870341014099496721630328278645418666846010691704607478618583702759992363440666993418619030237485528587348859969571210018137043207520873679779859033595683602914610709638916312478454916055545473221633606409724708696028461992993048321623395628300562083489975869230030253853581401883298121968097709955807128125717703814213374946135693482465779240925410304181161762236746438965258777036561492751897322832350264470109651028684236863863453034799410228775509009903378394078180158107480603541306787419495150822497132152335152382081196560442616580697347947792556206254746577283394520721393682679158130090477662086167460393641703540506200870833982607091601902070471831932709855794886131467656752368912414445109663468927715918836963812089976513565288183526265661154606184510371000495720884232369996410917023281870636175180679551376572685515980640045161757476665064106884666957407945238329414823085070747210388152585440273077770990333671176519998975097275996184604206230104472224768555489744621370539770018151143387894564794155492830470635273934388841594875393084091289985645588663930392051104536357260144631044455101765237971229462586093536716821344991507918890479698500839843555303817557228462300244470359852935558405916296939778886295214655414040792028096263060764367505016031376977151465698877716133072352613337799167179219973404271942995411056065453601516829793410895326726142588855615818388288582695433674459073497905268270441561905159008491777266372630340209367718068424961998918406373806319762040739193670103342329135335419182381705477006936409192271531274780774190191065964245729665770888748319170790740452179510858994088965617454948038899632792129251644790196681413385405504290040568173025658949656332072604421691737475582644975673193309609414388049324585213418610421345878547905089919239238240670786371910115373670903323073708900301437686857907321469741181750871907271887865017606432510987250313019159201012622516001258319683780906382274504985380888694092387571973596345164036388295699754417785150380131830678943815862890204618121327978319868674639621018783782049904638881850174425861615856074683028825227914579322954634063859961734032157807245227921118124821362908760449074989956045927413242794514720823949915844245133036528216502757696898601813320348745504005276867509108078858639177818880226880860153698627382262775877090267038563016970818927963393616955426011128367729807102190613380319987550961433766095743281028939801076446115680647708654494886791637454741914179160398294906454293198873078997162105263180433902649593299522562460930684878476123184947556938531192740878017513971549401590962327235546206017120678935469570738182945251346855973828764234143338538545341031989021377308702844049219097784730365112749011241905375716949594191878941641854089805056867260757041229615249209423075892783729793335293446264332228286362755756009030120417264752675322604412685239795010999525456296169562073322357795619464905029793139119048224950552311479544056437692328627989755986698654723109103267182248676336051106741141524528881899201588817314943169857321073818735950163288760978923464549212082128419006766237539515503682221618576295542072759012262138060337253082925184921597171530263922824496404124510138870057101850228102045178198553063544069270867580644270068574034634436614066904417903152051635066871255613987342693873185023433403225391414219203310978404072184647439281284412620410164329700948701061094124681226798191033805085548388680631479315970141905145560755752083307459972736322529876673827981609778389233792539527708142152684339570884293178601690227553423460960297781858083289759540747433923392738087226102070997422007826507974560679483941944526380714418760147258644861128263206735355567429823642814714723825856350317322955736900633849862950514709903695370280428935740432100547657975970179751833611997853610273553528795672528840685332212013002667056894172032851616503351600581209099378563136105626302511843848809702220821442403495264169158753813429148662735790773992687704559465915158198898831313177058835915973988412092258784739297656198087873377326469695818379707969579956681081500140259812707512992776525701105884650292069107903188837306959463965750480907773208396493472029505403939604296952024384457982388723203440964133528076407881957263948709443380323259507888517101775061496107027735719032462496263163664497084380949872931292696952127953772523644045488532406076567744063668757696294406661162860431869264191304277660845438588429188744205366937864374982488996481605404179486464111566092955246100497476024294163513179287035002462772622833288332143950315672970637150015285410515053421079521164722396143758595525436832305884020420263440449274478055310969440576770750979107724005937755567611493212997879663931438415318572137217089046143026672408032280973379133945403031877082644807405464105907632033186203763915342701131203203514139841371634905244135212136750870391361421359074554028364276440391917092941698073474361739811848050704459991414091910906368060875110547009146546960369007838561431617091998119075711580172639196710463018788807349221458547206162943042360881823914849066356943453387486407572486963992341273497201894777588080895197639512943323183290056366038309273686125776715462469982094254954831402576492123649669239497394393940435001608602087395114728463445841704799372757571366723273671849126038623554624256776944669670085710158944218023699356666634495485953831316661650731335037681658164987635320865519536502898749873824086781443628709699693332684843707045619472075530862340076471447882625021964603890715983852189973430870661701084238944657490266222963395163689418829189675508023295007808069307642850444028526226886562065083843488370841286408405995179171944870495679788572134709962320616891004076701728991254088188954976767715054713515850882317143287606970292153924007321093259544190859722164963953680207988984990534355965934596431101395881152524341088557906883945973901470242037618214405959112775371823367719993194130476438720390955131990275543052393742955496938069344690385859824176841818100705944642771906955759502254739362182748497192042439706714893582076055398112695109476809671099806255940187310692518142201409834744058458104606992077211891820740461351262603513035411741359893089935777895191119567444203039619948378556416673844040512848204935476660083467472748083960353014502319458670154921983224926050159387112957103241059010687892263371953163105845225607404221348170461195565939937076627394517111857452905081903545964370565125939743525174582269252919413493346647188490226187328242462821071539461355960592138050390314915847111284682742343637893097774741269413262218801327964257504383095924726521656076086091410223327612127871005392428990673558872853119482785357722937347527263635373552027119744197806557737285487673678383309891265969049323985309688523181462251122463390254408396971647207939310126648297881865402108371363805516579272102502358496484539118568613830520893655203890068243580539319300425603585312426613811374723430693135733955428933381342968354113073680607303793019229554816924450404097836952153693703579525425147725073623951604001222384685274639450523699411770999972815118901273469636757827476239267193575671996641470931712459372308747466538077177788315752571372571191536582411994123538565639435590653977599144606869997633857285286840458863902032682637908768893701537841188206767661324879447436633220399106905816124232362120481248862818703056391194565627112662861507692259090219272415626626358623493262360014624764247391708858808112597387733834860962557926001110158155386339397672054148016777922417638538242654792970371508207526373941009357566674163540681942878027766206000009028995405626044526698556386668319264052629521174959915154698806662998726189142263519578205919055160933105700905543034706534974600246164862003670372468386635879331671491778696549249623517422695406359027159166377148108323803971437071595511603371636753244899905132188196286097028992223908104452031510018387766957993523064309589713707267359407585545866068703911295913421475578281330980155125899608843527875412003693376421517036741749950607825639095452778537560031688828235746235669560248723515391852707911950267778034721971934431322569447452951182489356821802867119932102779609800661701391142909811693642030728681513106439081778625778863357240915493441945702488803941968907996342748548808311712354619124076892075890403442482966305300008876561772736984701556319636653431168294748336316091902368536517941589117446020711999810080777214067292003088850810896533318710398576697358378469016833767768163406569292201718005706616943174820336343350814981109252572276989400833873442344585171533627134154777372163608574842409137970932470336036226279245559844325892763525733805802257573206098388497151688489675654607657654236527113423659719294319324575403395853984942080252407130355951347951210612057533971019608432509713034995320845166472055849428674043781111327986871170176771960830368924204213781571047655701952269044535037571467161787400711079594645462537339283581180331961799567954086986546603450238804718872828433948810202127913781914854777194597023294412671368578765633400380372846761413970433697265425370729688674455131452123442307130107666380793440504107397956149753706603766237623997587823563587191784332950544403002339757967850646399086618476115308536954021855776080274847509337038051388544450455762591811936569456578326377252755258995454329860157312328398705830498807128033608968412142530052282363680150509937335121497977182657345002236472337832468719483738687302386556790175524011338415102959543298778292823031695400298834005024977148535709534634225887360785134285894002066437365118315601221523094644851306451415591112579115503554703023583634043160321762061881509435785770936773603707744954268008536247417798242761530298617364043957025046626330612776109648356071224922265647454622735262057436153410615210895368237769715728805670463586063198717862601359132246041416708855923428139590493807876593674977716844958728592246995617579211149138333605511849339234146661602981015319132133818990668243774488612411599719580251694506543369367184825985580137388243988177500142883080261292171568328706731364768742975694411497166251284318977666269646837283623152333029751436019090991724592553832110068240811190356092448782410807460525680369759898858635302044537501970154425377040992755049286508997493515806642361263830376005108271454787739409345634856345578858584024639568881897324779853624692239279819269744344948682949900964358680901176432016948716518240659017188131504431253087537927511053879112785161632412814401024083907758729133222272449303247930726300969726532368095218067137343413304086477566331663564425848344671122216642479434361861571120418387098078194226755676998508952552782432659588366828603937771476533360665808154975319085614273600942901932592120963443730395224400490819675354174986798201141558957416289618879429118000235468000476050078754145951464408212228966796338700162013150040380654692994230464959888659299173929901325099021676511428040170110016609022100278820805279900407036624644562906800511832131288200430556881906563925328581818569416626008612938725881116351777479021876641347708070538845855167731760436427606984258449575391125760197498912188322418580013878365337900202916315427282032439656345119120021996549240274528110306318798631711167961314617707935863371831570206047352192363410507192406664700529846191860955189431307602987024074887708644114015641708358591490244943613507354868299133334233354695447619509012535486535392511817934765535507748362279811865398405408728831342653202033448104665026931940843093387302286288017608508821151677403047991621852921648191689445571791136257136964811376215255464555762292102190886111579907091714283313305664736174464062173935263443712193994244357021251566451832833617709571101157530282464527496993150315946062890239519180550396135791371235696536976113728385123830637936750428389095375759204093671116152631131271563242683513133323138980095605570078455068993318155914973611422876890644281568668770792532882116254102403859501717361103137647502858031368387534672260207726962153273448432885376963132654931748758210312426651536475241965939634394135665437438522321694478384247805223996744201882612151606600847848458334252229786659911448232756308918512255860102703286517800104424554133255443817149962898652059714446024132024193617020322336462901611349387924043956578660370593435641956743143395389146482958558843498382409891806082397783025909494507061847980492364787268395850740047871100354182746786268155074812924081902077937477393317788573380083936068752512185859459136161554169269365894783470683232774754881276296946427284430183582195155027869767203496605690278568470133352010868242812295640059367235123845845052240668153550007029224599241781434643740807587888878423510668046603012196093105177227721508962486331110042188922655319315061187602331860798033054389553189993741199932930219617336979016046223455358593771045979558654624297293627800638779450617426184215055015106525051947802740054061822798552595202804601501295364023996240015617100314023774528722769935864909170333261717143101310717304011373467468064479003082205275097809239739610122003953181778803828255075430485338994862114886976383824210090898369420058458411499747455153912692360216410029984354091088738036785039094342515259463886278995887264076714868568285834005170248834541143800009678099525221945431174874985118315806746709828023330287408813510685729515499220108036662310901022288854415276623911050376513214884537343299856673166023640602358082553474553840607162000019986154242460480654123792734057222518738366674860837855733777295370199758999006343646410013397044711883995636046142179237967549814973852137232093268564669994299372326265910392484695407186139270989352929102683320478651646609919811949853593717645811935015528421720203987886625503846405037427510354811284942109367439245399004248051551625154234950102267577121686809578454289245480475061289112223948695134896907051370308513768348682117342694896963581477471406931045942067119644954073124938197488573782853327781603166002805572379834341789795621229920291637507402374342911200063979966179504247314479823229146447092770807841838635575199524746400429287564981087458311225379950112871165364973010342571009541235427464594251730642195036162860277497189699025128777771747212614436094833774985153418605942149955097720260130744605136264484798518958020841463821949118968519545979361210112910733590990202650158377965225700197237259708995387122090251321064817157296920957128686390428614321467074351661048338511158749774041911384369063989919147931296060898383910114478533996027465157002353821279106778426686164041311119105414401901554561219320022822364085317863948770086459558903980688621389686438535452066356084637415070732549057710350810896586802988166667034748929791708067984951922990787806506695264263993131942069902725298641
Mod(19,PRP22067)^18707==1 && 18707 | (prp22067-1) =>> PRP22067 is PRP to base 19
The above conclusion is obtained by exponentiating 19 to the power 18707 which is much cheaper than exponentiating to (PRP22067-1).
\\
\\
\\

Last fiddled with by a1call on 2023-02-15 at 14:29

2023-02-20, 17:11   #4
Happy5214

"Alexander"
Nov 2008
The Alamo City

22·5·72 Posts

Quote:
 Originally Posted by a1call Thank you for the link Happy5214, However there are more than one subject there which are above my comprehension. To clarify the concept I was referring to, here is a numeric example: Code: PRP22067 = 14081760257558730022545694985196062520493780635673898439426688430440965675893551690213884631042989421621898326633118368644188602409144124617319329324248968764792434142541280853494632202391967283366586824282513133712820015940364412849671771270204883586830761568659016331622397304133354365581981567716526076973712803217866397676020480235592542918136524343781021482665351592051541200684540430069483679614591643775527384380955219374420339766520110185178556989236953999725689826320432602075018065320793472649042557739178061091980016111354783934556539617148150952340536657776229921026250428234486396280099338986396666256248730051716141174760105195232917791043856310044910661949610100394791214455703577996444119401472984634881305379311740224678093886859469808162477254048080680996557160333833771652863480724103469843919778684837488270655102076236439476199832424194131066140587760689282194484067550953202950452950973883006399798695526320788922822803447908634827890454422311211862398625642413092783228047859335339965956732434900255391469391614246015174653465241836034100689886229611255174639837947322406632536641697795182274773021609220397383693614245936580826403125987674572539410721930334794879938689322202865160890652029897755424709961397535660280882463183065258480350819924022497396752230213200157526717620913746691434400673668084829809467836982339386561371394485899257219941470320784429256326061630799620522613354993235125162174766756704744900249908145550460972382479275017426051273722153157567151888063590247018589005091155742125722478241545102066982136409439719534033500903774999376830089639822089548759722257834099830673894110820550702813846633070547758010729638838889402145896789725281379573278762176017933541594180767443892395235799701657913623966346954044825824636920987970928011430590101569367489495529052909571576970901037870766781521473186515126658198397158823263684192392027121209547499980044176753337352021246944349041483232615162651438976761066250617010804895353841336931912023777182633477864382886604000582100999551500921343344496696927371197465222372330297940926139795776167035562165241189640848926727256649042530161553807062735665576763458611277642071462240921009886604244029871045601003061615030429163530592899753082834331361878946733125232794568380992433301754357446683617817756949061916048039817819968064387278471830583509337314077557563226602388714491376852651272867201032419444293101859687359978573573385260971267110267380716423896203616928435524425073534367683804133295726573499530359346062659908022382261484648490930928332605938197392982546604361914393603531889012786099986625501663569447363665975581252661587952594093166953375870200214622304301976628590950562412557609374458338605937117367953873900682250792027303635488694403444270980951296954131504526520831998570615824636440562621028423590093115998465792281375725186644362001312734613407431732039560143500609538659898424358552677194902590669123535684934779622387136349438007695931898906624105064023498485279035961237263721775696409559667702032221458544537351461997507819671612197087564090962487484561963518003566799630410285605870154553620408033131394604977138363872930511905924709023253161173361869860896809605542371542673256863950436999800620635198996310777828220687049507346504179885384347124623216785284437297027416665894504052411351138053585771839398862759051048859071464353655869050321681487878908874222761710839713581834333029662287074811457957645825596522296582080519950893937525644720272870060553163263488133890651979548255893700795871770568591679505233160896175119675403470245688984409107739095591131331294482238215982166212597556550136875684814645016088024553298069979537171026956014100497009339010162813775333597375819957284524134385859085651269842515829153804556196284641543110704264690490287636460145235427360337455681170839756718215839847736008345655653160425975007965655792495080800361754289325136737762394772454966381014209823434893920924628503129510028930949303162051407426799730398035735181759524308023089191473049056940257179881684533752552006286044279475026204548623345668819297373202974861547755100785274192498565768379541435405559755617208621132235892747890058193035288220307186242093418854685225586727302368799512597840300359738743595266924317407050317862414409145497020767048041608725759110982101232628615571387910392424782140763307890815094248714034356559699260292035152714044284673679757608442328000340194761527795033084013912539198997044225660630235487086190119276070823114352091051170635568797731795770328528177282518810918942017909142956490953098774629963101863128203699241399984611212327086212580339845185951437879365823104681610981509039041026055184470955913787490932383901383559549058627879003503161420987977638215407468052792394073371401059772665431068396760025998376520730261740591618111869715794924137436104124650527790492717880726465144455731897778294847332641463340910960612007474245353495767516207019395274630654924357010903159779301158970485890852412860595787909409197445708891083273531992884553997631930185960893468016664359480574736984379540431244382238510956392077844556590055060406271776991229526876750918193229241115891458261932004973867586076884250341483637214629595528511353973738990762715951680186767259540775310890776326080409029180533095042816480099561336683272869820672172448769803508749641955571204044803547363157580553142844666217311160306858786730514980432811940620487798344350073549893431255711685353962547741207578584193703940856550247449767616688052501446642843231347725292530869874519662195199084477899470842627450751170679113060903227591037838433376835440705962195568080462489116135699138837480290382537508545493025164310407014671079122330128008601446635336497914310051450390443783393802888447507106066161989156353886456606035329793509614090598533355836706677801471303890190798996453380280463283627145592714141590404590945239225615518543962381311959263057794047008278178638434956048987084543824166151685522826768866001961531265275465394703878824181950693304081949102682302398613709449412685086059764581593257643236509075811029809788222058390183882148898733509834768453005487412912163214375165847676509602573769384867529964864208564697445237310743732750593660305613677640838521467695948608257009502851250465730165160886369194613558185792076011280573430431331477657620609461087598235854223054245789403011994964157392559862674196301121801091461520297341836658719430509475388552464730488383850178515762271785551931097124768906322411736942342021335401129163710825039196770821401904912310443975216988144263934153898197736691819352612829532176360827629983683881315207611186289460501083545960278577948109731351526689129774962054199943495372291656417660170045519109405007392442750800398900131556175281753127036849550045236339074092482010572276243117452843608501802091998056066725224838098968844789347378060960896212400145220317322160831046490762435981164806808099925733650535438170560119806475581528403872038985040535944652630825068615041469764782942614270915468797635543999868688746043035769554981413585993631029495972055426475808220256068825897504909486244235531101352744833507165396293245925290287596429252136370676097732435906025150848427681894697402122513236669048446029077477009008905561089760206482319198071515854727994642296564715545584763213453614434269870341014099496721630328278645418666846010691704607478618583702759992363440666993418619030237485528587348859969571210018137043207520873679779859033595683602914610709638916312478454916055545473221633606409724708696028461992993048321623395628300562083489975869230030253853581401883298121968097709955807128125717703814213374946135693482465779240925410304181161762236746438965258777036561492751897322832350264470109651028684236863863453034799410228775509009903378394078180158107480603541306787419495150822497132152335152382081196560442616580697347947792556206254746577283394520721393682679158130090477662086167460393641703540506200870833982607091601902070471831932709855794886131467656752368912414445109663468927715918836963812089976513565288183526265661154606184510371000495720884232369996410917023281870636175180679551376572685515980640045161757476665064106884666957407945238329414823085070747210388152585440273077770990333671176519998975097275996184604206230104472224768555489744621370539770018151143387894564794155492830470635273934388841594875393084091289985645588663930392051104536357260144631044455101765237971229462586093536716821344991507918890479698500839843555303817557228462300244470359852935558405916296939778886295214655414040792028096263060764367505016031376977151465698877716133072352613337799167179219973404271942995411056065453601516829793410895326726142588855615818388288582695433674459073497905268270441561905159008491777266372630340209367718068424961998918406373806319762040739193670103342329135335419182381705477006936409192271531274780774190191065964245729665770888748319170790740452179510858994088965617454948038899632792129251644790196681413385405504290040568173025658949656332072604421691737475582644975673193309609414388049324585213418610421345878547905089919239238240670786371910115373670903323073708900301437686857907321469741181750871907271887865017606432510987250313019159201012622516001258319683780906382274504985380888694092387571973596345164036388295699754417785150380131830678943815862890204618121327978319868674639621018783782049904638881850174425861615856074683028825227914579322954634063859961734032157807245227921118124821362908760449074989956045927413242794514720823949915844245133036528216502757696898601813320348745504005276867509108078858639177818880226880860153698627382262775877090267038563016970818927963393616955426011128367729807102190613380319987550961433766095743281028939801076446115680647708654494886791637454741914179160398294906454293198873078997162105263180433902649593299522562460930684878476123184947556938531192740878017513971549401590962327235546206017120678935469570738182945251346855973828764234143338538545341031989021377308702844049219097784730365112749011241905375716949594191878941641854089805056867260757041229615249209423075892783729793335293446264332228286362755756009030120417264752675322604412685239795010999525456296169562073322357795619464905029793139119048224950552311479544056437692328627989755986698654723109103267182248676336051106741141524528881899201588817314943169857321073818735950163288760978923464549212082128419006766237539515503682221618576295542072759012262138060337253082925184921597171530263922824496404124510138870057101850228102045178198553063544069270867580644270068574034634436614066904417903152051635066871255613987342693873185023433403225391414219203310978404072184647439281284412620410164329700948701061094124681226798191033805085548388680631479315970141905145560755752083307459972736322529876673827981609778389233792539527708142152684339570884293178601690227553423460960297781858083289759540747433923392738087226102070997422007826507974560679483941944526380714418760147258644861128263206735355567429823642814714723825856350317322955736900633849862950514709903695370280428935740432100547657975970179751833611997853610273553528795672528840685332212013002667056894172032851616503351600581209099378563136105626302511843848809702220821442403495264169158753813429148662735790773992687704559465915158198898831313177058835915973988412092258784739297656198087873377326469695818379707969579956681081500140259812707512992776525701105884650292069107903188837306959463965750480907773208396493472029505403939604296952024384457982388723203440964133528076407881957263948709443380323259507888517101775061496107027735719032462496263163664497084380949872931292696952127953772523644045488532406076567744063668757696294406661162860431869264191304277660845438588429188744205366937864374982488996481605404179486464111566092955246100497476024294163513179287035002462772622833288332143950315672970637150015285410515053421079521164722396143758595525436832305884020420263440449274478055310969440576770750979107724005937755567611493212997879663931438415318572137217089046143026672408032280973379133945403031877082644807405464105907632033186203763915342701131203203514139841371634905244135212136750870391361421359074554028364276440391917092941698073474361739811848050704459991414091910906368060875110547009146546960369007838561431617091998119075711580172639196710463018788807349221458547206162943042360881823914849066356943453387486407572486963992341273497201894777588080895197639512943323183290056366038309273686125776715462469982094254954831402576492123649669239497394393940435001608602087395114728463445841704799372757571366723273671849126038623554624256776944669670085710158944218023699356666634495485953831316661650731335037681658164987635320865519536502898749873824086781443628709699693332684843707045619472075530862340076471447882625021964603890715983852189973430870661701084238944657490266222963395163689418829189675508023295007808069307642850444028526226886562065083843488370841286408405995179171944870495679788572134709962320616891004076701728991254088188954976767715054713515850882317143287606970292153924007321093259544190859722164963953680207988984990534355965934596431101395881152524341088557906883945973901470242037618214405959112775371823367719993194130476438720390955131990275543052393742955496938069344690385859824176841818100705944642771906955759502254739362182748497192042439706714893582076055398112695109476809671099806255940187310692518142201409834744058458104606992077211891820740461351262603513035411741359893089935777895191119567444203039619948378556416673844040512848204935476660083467472748083960353014502319458670154921983224926050159387112957103241059010687892263371953163105845225607404221348170461195565939937076627394517111857452905081903545964370565125939743525174582269252919413493346647188490226187328242462821071539461355960592138050390314915847111284682742343637893097774741269413262218801327964257504383095924726521656076086091410223327612127871005392428990673558872853119482785357722937347527263635373552027119744197806557737285487673678383309891265969049323985309688523181462251122463390254408396971647207939310126648297881865402108371363805516579272102502358496484539118568613830520893655203890068243580539319300425603585312426613811374723430693135733955428933381342968354113073680607303793019229554816924450404097836952153693703579525425147725073623951604001222384685274639450523699411770999972815118901273469636757827476239267193575671996641470931712459372308747466538077177788315752571372571191536582411994123538565639435590653977599144606869997633857285286840458863902032682637908768893701537841188206767661324879447436633220399106905816124232362120481248862818703056391194565627112662861507692259090219272415626626358623493262360014624764247391708858808112597387733834860962557926001110158155386339397672054148016777922417638538242654792970371508207526373941009357566674163540681942878027766206000009028995405626044526698556386668319264052629521174959915154698806662998726189142263519578205919055160933105700905543034706534974600246164862003670372468386635879331671491778696549249623517422695406359027159166377148108323803971437071595511603371636753244899905132188196286097028992223908104452031510018387766957993523064309589713707267359407585545866068703911295913421475578281330980155125899608843527875412003693376421517036741749950607825639095452778537560031688828235746235669560248723515391852707911950267778034721971934431322569447452951182489356821802867119932102779609800661701391142909811693642030728681513106439081778625778863357240915493441945702488803941968907996342748548808311712354619124076892075890403442482966305300008876561772736984701556319636653431168294748336316091902368536517941589117446020711999810080777214067292003088850810896533318710398576697358378469016833767768163406569292201718005706616943174820336343350814981109252572276989400833873442344585171533627134154777372163608574842409137970932470336036226279245559844325892763525733805802257573206098388497151688489675654607657654236527113423659719294319324575403395853984942080252407130355951347951210612057533971019608432509713034995320845166472055849428674043781111327986871170176771960830368924204213781571047655701952269044535037571467161787400711079594645462537339283581180331961799567954086986546603450238804718872828433948810202127913781914854777194597023294412671368578765633400380372846761413970433697265425370729688674455131452123442307130107666380793440504107397956149753706603766237623997587823563587191784332950544403002339757967850646399086618476115308536954021855776080274847509337038051388544450455762591811936569456578326377252755258995454329860157312328398705830498807128033608968412142530052282363680150509937335121497977182657345002236472337832468719483738687302386556790175524011338415102959543298778292823031695400298834005024977148535709534634225887360785134285894002066437365118315601221523094644851306451415591112579115503554703023583634043160321762061881509435785770936773603707744954268008536247417798242761530298617364043957025046626330612776109648356071224922265647454622735262057436153410615210895368237769715728805670463586063198717862601359132246041416708855923428139590493807876593674977716844958728592246995617579211149138333605511849339234146661602981015319132133818990668243774488612411599719580251694506543369367184825985580137388243988177500142883080261292171568328706731364768742975694411497166251284318977666269646837283623152333029751436019090991724592553832110068240811190356092448782410807460525680369759898858635302044537501970154425377040992755049286508997493515806642361263830376005108271454787739409345634856345578858584024639568881897324779853624692239279819269744344948682949900964358680901176432016948716518240659017188131504431253087537927511053879112785161632412814401024083907758729133222272449303247930726300969726532368095218067137343413304086477566331663564425848344671122216642479434361861571120418387098078194226755676998508952552782432659588366828603937771476533360665808154975319085614273600942901932592120963443730395224400490819675354174986798201141558957416289618879429118000235468000476050078754145951464408212228966796338700162013150040380654692994230464959888659299173929901325099021676511428040170110016609022100278820805279900407036624644562906800511832131288200430556881906563925328581818569416626008612938725881116351777479021876641347708070538845855167731760436427606984258449575391125760197498912188322418580013878365337900202916315427282032439656345119120021996549240274528110306318798631711167961314617707935863371831570206047352192363410507192406664700529846191860955189431307602987024074887708644114015641708358591490244943613507354868299133334233354695447619509012535486535392511817934765535507748362279811865398405408728831342653202033448104665026931940843093387302286288017608508821151677403047991621852921648191689445571791136257136964811376215255464555762292102190886111579907091714283313305664736174464062173935263443712193994244357021251566451832833617709571101157530282464527496993150315946062890239519180550396135791371235696536976113728385123830637936750428389095375759204093671116152631131271563242683513133323138980095605570078455068993318155914973611422876890644281568668770792532882116254102403859501717361103137647502858031368387534672260207726962153273448432885376963132654931748758210312426651536475241965939634394135665437438522321694478384247805223996744201882612151606600847848458334252229786659911448232756308918512255860102703286517800104424554133255443817149962898652059714446024132024193617020322336462901611349387924043956578660370593435641956743143395389146482958558843498382409891806082397783025909494507061847980492364787268395850740047871100354182746786268155074812924081902077937477393317788573380083936068752512185859459136161554169269365894783470683232774754881276296946427284430183582195155027869767203496605690278568470133352010868242812295640059367235123845845052240668153550007029224599241781434643740807587888878423510668046603012196093105177227721508962486331110042188922655319315061187602331860798033054389553189993741199932930219617336979016046223455358593771045979558654624297293627800638779450617426184215055015106525051947802740054061822798552595202804601501295364023996240015617100314023774528722769935864909170333261717143101310717304011373467468064479003082205275097809239739610122003953181778803828255075430485338994862114886976383824210090898369420058458411499747455153912692360216410029984354091088738036785039094342515259463886278995887264076714868568285834005170248834541143800009678099525221945431174874985118315806746709828023330287408813510685729515499220108036662310901022288854415276623911050376513214884537343299856673166023640602358082553474553840607162000019986154242460480654123792734057222518738366674860837855733777295370199758999006343646410013397044711883995636046142179237967549814973852137232093268564669994299372326265910392484695407186139270989352929102683320478651646609919811949853593717645811935015528421720203987886625503846405037427510354811284942109367439245399004248051551625154234950102267577121686809578454289245480475061289112223948695134896907051370308513768348682117342694896963581477471406931045942067119644954073124938197488573782853327781603166002805572379834341789795621229920291637507402374342911200063979966179504247314479823229146447092770807841838635575199524746400429287564981087458311225379950112871165364973010342571009541235427464594251730642195036162860277497189699025128777771747212614436094833774985153418605942149955097720260130744605136264484798518958020841463821949118968519545979361210112910733590990202650158377965225700197237259708995387122090251321064817157296920957128686390428614321467074351661048338511158749774041911384369063989919147931296060898383910114478533996027465157002353821279106778426686164041311119105414401901554561219320022822364085317863948770086459558903980688621389686438535452066356084637415070732549057710350810896586802988166667034748929791708067984951922990787806506695264263993131942069902725298641 Mod(19,PRP22067)^18707==1 && 18707 | (prp22067-1) =>> PRP22067 is PRP to base 19 The above conclusion is obtained by exponentiating 19 to the power 18707 which is much cheaper than exponentiating to (PRP22067-1). \\ \\ \\
If you're looking for that direction of the proof, it's almost immediate:

Let $$n - 1 = xy$$, where $$x$$ is the smaller number you want to take the power of. Then $$a^x \equiv 1 \pmod{n} \Rightarrow a^{n-1} = a^{xy} = (a^x)^y \equiv 1^y \equiv 1 \pmod{n}$$.

 2023-02-20, 18:09 #5 a1call     "Rashid Naimi" Oct 2015 Remote to Here/There 22·5·7·17 Posts Thank you very much for the elegant proof Happy5214. However the concept is simple enough that even I could figure it out. I am more interested in discussions about how the concept can (or cannot) be utilized to perform a PRP test cheaper (and perhaps much cheaper) by exponentiating to a smaller exponent than the full value of the candidate-1. Thanks again for taking the time to reply.
2023-02-20, 18:57   #6
paulunderwood

Sep 2002
Database er0rr

2×5×467 Posts

Quote:
 Originally Posted by a1call I am more interested in discussions about how the concept can (or cannot) be utilized to perform a PRP test cheaper (and perhaps much cheaper) by exponentiating to a smaller exponent than the full value of the candidate-1. Thanks again for taking the time to reply.
Code:
 n=2^17-1;facs=factor(n-1)~[1,];foreach(facs,fac,R=lift(Mod(3,n)^fac);print([n,R==1,fac,R]))
[131071, 0, 2, 9]
[131071, 0, 3, 27]
[131071, 0, 5, 243]
[131071, 0, 17, 35228]
[131071, 0, 257, 73071]
I guess it works in exceptional cases. Perhaps someone can tell us what these are.

2023-02-20, 19:26   #7
a1call

"Rashid Naimi"
Oct 2015
Remote to Here/There

22×5×7×17 Posts

It does not work for Mersennes. It could work for their factors and it could work for Fermats.
My PARI is too old for "foreach".

Quote:
 Mod(17,257)^64 Mod(1, 257) 64 | (257-1)

Quote:
 Mod(17,2^(2^5)+1)^4 Mod(83521, 4294967297) 4 | (4294967297-1)

Code:
Mod(257,2^(2^4)+1)^64
Mod(1, 65537)
64 | (F4-1)

Last fiddled with by a1call on 2023-02-20 at 19:39

 2023-02-20, 20:33 #8 a1call     "Rashid Naimi" Oct 2015 Remote to Here/There 22×5×7×17 Posts The test for Fermats is not valid for the bases I chose since the test would be positive regardless of primality. I have some work in progress that might work for other bases. Or, I could be wrong as usual.
2023-02-20, 22:06   #9
chalsall
If I May

"Chris Halsall"
Sep 2002
Barbados

3×3,767 Posts

Quote:
 Originally Posted by a1call Or, I could be wrong as usual.
It takes someone strong to do something like this. Thank you for doing that. It takes a serious person to do that kind of thing. Seriously... 8^)

 2023-02-20, 22:56 #10 a1call     "Rashid Naimi" Oct 2015 Remote to Here/There 94C16 Posts Thank you chalsall, I rather risk being wrong than not trying stuff. So here is a Mersenne number test: Mod(5,2^11-1)^44 = Mod(1, 2047) && 44 !| M11-1 Which deduces that M11 is not PRP to base 5 obtained by exponentiating to power of 44 rather than 2046. And to think that it only took me the whole afternoon to find it. If that's not cheap then I don't know what is. Last fiddled with by a1call on 2023-02-20 at 23:05
 2023-02-21, 03:23 #11 a1call     "Rashid Naimi" Oct 2015 Remote to Here/There 22×5×7×17 Posts Sometimes failure is a good thing. When a candidate fails a PRP test for any given base then it is definitely a composite and not probably a composite. It is not easy (for me) to get the right base but there might just be a fast algorithm for getting these cheap bases. After all they do exist. Code: q=29 p=2^q-1 Mod(7,p)^39672 = Mod(1, 536870911) && 39672 !| M29-1 Which deduces that M29 is not PRP to base 7 obtained by exponentiating to power of 39672 rather than 536870910. Code:  q=37 p=2^q-1 Mod(3,p)^308159088 = Mod(1, 137438953471) && 308159088 !| M37-1 Which deduces that M37 is not PRP to base 3 obtained by exponentiating to power of 308159088 rather than 137438953470. Last fiddled with by a1call on 2023-02-21 at 04:05

 Thread Tools

 Similar Threads Thread Thread Starter Forum Replies Last Post ewmayer Computer Science & Computational Number Theory 89 2023-06-02 22:21 carpetpool carpetpool 2 2020-04-12 01:04 davar55 Homework Help 67 2017-05-23 13:16 Erasmus Math 46 2014-08-08 20:05 T.Rex Math 2 2004-09-11 07:26

All times are UTC. The time now is 08:47.

Fri Jun 9 08:47:07 UTC 2023 up 295 days, 6:15, 0 users, load averages: 1.03, 1.01, 0.92

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2023, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔