Cheap Cyclic Fermat's Tests

[a1call]

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.

[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".

[a1call]

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:

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).
\\
\\
\\

[Happy5214]

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:

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}\).

[a1call]

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.

[paulunderwood]

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.

 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.

[a1call]

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".

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

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

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

[a1call]

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.

[chalsall]

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^)

[a1call]

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.

[a1call]

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.

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.

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.