What is the next Prime that is 3 mod 4 from this one?
in [Cryptography]
|
Prev: Adi Shamir's Cube Attacks
Next: Merry Christmas 7
From: amzoti on 28 Aug 2008 17:58 Hi, I have this prime (base 10): 104438888141315250667960271984652954583126906099213500902258875644433817202232\ 269071044404666980978393011158573789036269186012707927049545451721867301692842\ 745914600186688577976298222932119236830334623520436805101030915567415569746034\ 717694639407653515728499489528482163370092181171673897245183497945589701030633\ 346859075135836513878225037226911796898519432244453568741552200715163863814145\ 617842062127782267499502799027867345862954439173691976629900551150544617766815\ 444623488266596168079657690319911608934763494718777890652800800475669257166692\ 296412256617458277670733245237100127216377684122931832490312574071357414100512\ 456196591388889975346173534797001169325631675166067895083002751025580484610558\ 346505544661509044430958305077580850929704003968005743534225392656624089819586\ 363158888893636412992005930845566945403401039147823878418988859467233624276379\ 513817635322284552464404009425896243361335403610464388192523848922401019419308\ 891166616558422942466816544168892779046060826486420423771700205474433798894197\ 466121469968970652154300626260453589099812575227594260877217437610731421774923\ 304821790494440983623823577230674987439676046337648021513346133347839568274660\ 8242585133953883882226786118030184028136755970045385534758453247 It is a 3 mod 4 prime. What is the next closest prime that is also 3 mod 4? Is there an efficient algorithm to find those? Thanks for any input! ~A
From: Greg Rose on 28 Aug 2008 18:01 In article <2958f163-e345-41c5-843d-a0ac976471de(a)l64g2000hse.googlegroups.com>, amzoti <amzoti(a)gmail.com> wrote: >Hi, > >I have this prime (base 10): > >104438888141315250667960271984652954583126906099213500902258875644433817202232\ >269071044404666980978393011158573789036269186012707927049545451721867301692842\ >745914600186688577976298222932119236830334623520436805101030915567415569746034\ >717694639407653515728499489528482163370092181171673897245183497945589701030633\ >346859075135836513878225037226911796898519432244453568741552200715163863814145\ >617842062127782267499502799027867345862954439173691976629900551150544617766815\ >444623488266596168079657690319911608934763494718777890652800800475669257166692\ >296412256617458277670733245237100127216377684122931832490312574071357414100512\ >456196591388889975346173534797001169325631675166067895083002751025580484610558\ >346505544661509044430958305077580850929704003968005743534225392656624089819586\ >363158888893636412992005930845566945403401039147823878418988859467233624276379\ >513817635322284552464404009425896243361335403610464388192523848922401019419308\ >891166616558422942466816544168892779046060826486420423771700205474433798894197\ >466121469968970652154300626260453589099812575227594260877217437610731421774923\ >304821790494440983623823577230674987439676046337648021513346133347839568274660\ >8242585133953883882226786118030184028136755970045385534758453247 > >It is a 3 mod 4 prime. > >What is the next closest prime that is also 3 mod 4? >Is there an efficient algorithm to find those? Add 4, test for primality, loop until successful. For efficiency, you probably want to do some sort of sieve implementation, but that should be quick enough... you'll probably find the answer before you could code something smarter. Greg. -- Greg Rose 232B EC8F 44C6 C853 D68F E107 E6BF CD2F 1081 A37C Qualcomm Australia: http://www.qualcomm.com.au
From: Mike Scott on 28 Aug 2008 18:11 amzoti wrote: > Hi, > > I have this prime (base 10): > > 104438888141315250667960271984652954583126906099213500902258875644433817202232\ > 269071044404666980978393011158573789036269186012707927049545451721867301692842\ > 745914600186688577976298222932119236830334623520436805101030915567415569746034\ > 717694639407653515728499489528482163370092181171673897245183497945589701030633\ > 346859075135836513878225037226911796898519432244453568741552200715163863814145\ > 617842062127782267499502799027867345862954439173691976629900551150544617766815\ > 444623488266596168079657690319911608934763494718777890652800800475669257166692\ > 296412256617458277670733245237100127216377684122931832490312574071357414100512\ > 456196591388889975346173534797001169325631675166067895083002751025580484610558\ > 346505544661509044430958305077580850929704003968005743534225392656624089819586\ > 363158888893636412992005930845566945403401039147823878418988859467233624276379\ > 513817635322284552464404009425896243361335403610464388192523848922401019419308\ > 891166616558422942466816544168892779046060826486420423771700205474433798894197\ > 466121469968970652154300626260453589099812575227594260877217437610731421774923\ > 304821790494440983623823577230674987439676046337648021513346133347839568274660\ > 8242585133953883882226786118030184028136755970045385534758453247 > > It is a 3 mod 4 prime. > > What is the next closest prime that is also 3 mod 4? > > Is there an efficient algorithm to find those? Keep adding 4 until you get the next prime. In this case p+432 is the next nearest prime. Mike > > Thanks for any input! > > ~A
From: amzoti on 28 Aug 2008 18:14 On Aug 28, 3:11 pm, Mike Scott <msc...(a)indigo.ie> wrote: > amzoti wrote: > > Hi, > > > I have this prime (base 10): > > > 104438888141315250667960271984652954583126906099213500902258875644433817202232\ > > 269071044404666980978393011158573789036269186012707927049545451721867301692842\ > > 745914600186688577976298222932119236830334623520436805101030915567415569746034\ > > 717694639407653515728499489528482163370092181171673897245183497945589701030633\ > > 346859075135836513878225037226911796898519432244453568741552200715163863814145\ > > 617842062127782267499502799027867345862954439173691976629900551150544617766815\ > > 444623488266596168079657690319911608934763494718777890652800800475669257166692\ > > 296412256617458277670733245237100127216377684122931832490312574071357414100512\ > > 456196591388889975346173534797001169325631675166067895083002751025580484610558\ > > 346505544661509044430958305077580850929704003968005743534225392656624089819586\ > > 363158888893636412992005930845566945403401039147823878418988859467233624276379\ > > 513817635322284552464404009425896243361335403610464388192523848922401019419308\ > > 891166616558422942466816544168892779046060826486420423771700205474433798894197\ > > 466121469968970652154300626260453589099812575227594260877217437610731421774923\ > > 304821790494440983623823577230674987439676046337648021513346133347839568274660\ > > 8242585133953883882226786118030184028136755970045385534758453247 > > > It is a 3 mod 4 prime. > > > What is the next closest prime that is also 3 mod 4? > > > Is there an efficient algorithm to find those? > > Keep adding 4 until you get the next prime. In this case p+432 is the > next nearest prime. > > Mike > > > > > Thanks for any input! > > > ~A > > Thanks to you and Greg! I just found it and it agrees with your number! ~A
From: Mensanator on 28 Aug 2008 18:38
On Aug 28, 4:58 pm, amzoti <amz...(a)gmail.com> wrote: > Hi, > > I have this prime (base 10): > > 104438888141315250667960271984652954583126906099213500902258875644433817202232\ > 269071044404666980978393011158573789036269186012707927049545451721867301692842\ > 745914600186688577976298222932119236830334623520436805101030915567415569746034\ > 717694639407653515728499489528482163370092181171673897245183497945589701030633\ > 346859075135836513878225037226911796898519432244453568741552200715163863814145\ > 617842062127782267499502799027867345862954439173691976629900551150544617766815\ > 444623488266596168079657690319911608934763494718777890652800800475669257166692\ > 296412256617458277670733245237100127216377684122931832490312574071357414100512\ > 456196591388889975346173534797001169325631675166067895083002751025580484610558\ > 346505544661509044430958305077580850929704003968005743534225392656624089819586\ > 363158888893636412992005930845566945403401039147823878418988859467233624276379\ > 513817635322284552464404009425896243361335403610464388192523848922401019419308\ > 891166616558422942466816544168892779046060826486420423771700205474433798894197\ > 466121469968970652154300626260453589099812575227594260877217437610731421774923\ > 304821790494440983623823577230674987439676046337648021513346133347839568274660\ > 8242585133953883882226786118030184028136755970045385534758453247 > > It is a 3 mod 4 prime. > > What is the next closest prime that is also 3 mod 4? > > Is there an efficient algorithm to find those? > > Thanks for any input! # Python import gmpy a =['10443888814131525066796027198465295458312690', \ '60992135009022588756444338172022322690710444', \ '04666980978393011158573789036269186012707927', \ '04954545172186730169284274591460018668857797', \ '62982229321192368303346235204368051010309155', \ '67415569746034717694639407653515728499489528', \ '48216337009218117167389724518349794558970103', \ '06333468590751358365138782250372269117968985', \ '19432244453568741552200715163863814145617842', \ '06212778226749950279902786734586295443917369', \ '19766299005511505446177668154446234882665961', \ '68079657690319911608934763494718777890652800', \ '80047566925716669229641225661745827767073324', \ '52371001272163776841229318324903125740713574', \ '14100512456196591388889975346173534797001169', \ '32563167516606789508300275102558048461055834', \ '65055446615090444309583050775808509297040039', \ '68005743534225392656624089819586363158888893', \ '63641299200593084556694540340103914782387841', \ '89888594672336242763795138176353222845524644', \ '04009425896243361335403610464388192523848922', \ '40101941930889116661655842294246681654416889', \ '27790460608264864204237717002054744337988941', \ '97466121469968970652154300626260453589099812', \ '57522759426087721743761073142177492330482179', \ '04944409836238235772306749874396760463376480', \ '21513346133347839568274660824258513395388388', \ '2226786118030184028136755970045385534758453247'] n = gmpy.mpz(''.join(a)) n = gmpy.next_prime(n) while (n % 4) != 3: n = gmpy.next_prime(n) print n ## 1044388881413152506679602719846529545831269060992135 ## 0090225887564443381720223226907104440466698097839301 ## 1158573789036269186012707927049545451721867301692842 ## 7459146001866885779762982229321192368303346235204368 ## 0510103091556741556974603471769463940765351572849948 ## 9528482163370092181171673897245183497945589701030633 ## 3468590751358365138782250372269117968985194322444535 ## 6874155220071516386381414561784206212778226749950279 ## 9027867345862954439173691976629900551150544617766815 ## 4446234882665961680796576903199116089347634947187778 ## 9065280080047566925716669229641225661745827767073324 ## 5237100127216377684122931832490312574071357414100512 ## 4561965913888899753461735347970011693256316751660678 ## 9508300275102558048461055834650554466150904443095830 ## 5077580850929704003968005743534225392656624089819586 ## 3631588888936364129920059308455669454034010391478238 ## 7841898885946723362427637951381763532228455246440400 ## 9425896243361335403610464388192523848922401019419308 ## 8911666165584229424668165441688927790460608264864204 ## 2377170020547443379889419746612146996897065215430062 ## 6260453589099812575227594260877217437610731421774923 ## 3048217904944409836238235772306749874396760463376480 ## 2151334613334783956827466082425851339538838822267861 ## 18030184028136755970045385534758453679 > > ~A |