Prev: Adi Shamir's Cube Attacks
Next: Merry Christmas 7
From: amzoti on 29 Aug 2008 16:28
On Aug 28, 3:38 pm, Mensanator <mensana...(a)aol.com> wrote:
> On Aug 28, 4:58 pm, amzoti <amz...(a)gmail.com> wrote:
>
>
>
> > Hi,
>
> > I have this prime (base 10):
>
> > 104438888141315250667960271984652954583126906099213500902258875644433817202­232\
> > 269071044404666980978393011158573789036269186012707927049545451721867301692­842\
> > 745914600186688577976298222932119236830334623520436805101030915567415569746­034\
> > 717694639407653515728499489528482163370092181171673897245183497945589701030­633\
> > 346859075135836513878225037226911796898519432244453568741552200715163863814­145\
> > 617842062127782267499502799027867345862954439173691976629900551150544617766­815\
> > 444623488266596168079657690319911608934763494718777890652800800475669257166­692\
> > 296412256617458277670733245237100127216377684122931832490312574071357414100­512\
> > 456196591388889975346173534797001169325631675166067895083002751025580484610­558\
> > 346505544661509044430958305077580850929704003968005743534225392656624089819­586\
> > 363158888893636412992005930845566945403401039147823878418988859467233624276­379\
> > 513817635322284552464404009425896243361335403610464388192523848922401019419­308\
> > 891166616558422942466816544168892779046060826486420423771700205474433798894­197\
> > 466121469968970652154300626260453589099812575227594260877217437610731421774­923\
> > 304821790494440983623823577230674987439676046337648021513346133347839568274­660\
> > 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
>
>

Python has such a nice syntax and large integer math package!

Here is a curious example.

prime = 1299853

The next prime that is 3 mod 4 from this one is

next_prime_3_mod_4 = 1299887 (it is only 34 away)

Trying to Add 4 to prime, testing for primality, and looping until
successful seems to miss this one.

What am I missing?

Thanks

~A
What am I missing - probably something stupid?
From: Gordon Burditt on 29 Aug 2008 16:35
>Here is a curious example.
>
>prime = 1299853

The original prime in the original example was stated to be 3 mod 4.
Yours isn't. It's 1 mod 4.

>The next prime that is 3 mod 4 from this one is
>
>next_prime_3_mod_4 = 1299887 (it is only 34 away)
>
>Trying to Add 4 to prime, testing for primality, and looping until
>successful seems to miss this one.
>
>What am I missing?
From: Jean-Claude Arbaut on 29 Aug 2008 16:35
amzoti wrote:
> On Aug 28, 3:38 pm, Mensanator <mensana...(a)aol.com> wrote:
>> On Aug 28, 4:58 pm, amzoti <amz...(a)gmail.com> wrote:
>>
>>
>>
>>> Hi,
>>> I have this prime (base 10):
>>> 104438888141315250667960271984652954583126906099213500902258875644433817202�232\
>>> 269071044404666980978393011158573789036269186012707927049545451721867301692�842\
>>> 745914600186688577976298222932119236830334623520436805101030915567415569746�034\
>>> 717694639407653515728499489528482163370092181171673897245183497945589701030�633\
>>> 346859075135836513878225037226911796898519432244453568741552200715163863814�145\
>>> 617842062127782267499502799027867345862954439173691976629900551150544617766�815\
>>> 444623488266596168079657690319911608934763494718777890652800800475669257166�692\
>>> 296412256617458277670733245237100127216377684122931832490312574071357414100�512\
>>> 456196591388889975346173534797001169325631675166067895083002751025580484610�558\
>>> 346505544661509044430958305077580850929704003968005743534225392656624089819�586\
>>> 363158888893636412992005930845566945403401039147823878418988859467233624276�379\
>>> 513817635322284552464404009425896243361335403610464388192523848922401019419�308\
>>> 891166616558422942466816544168892779046060826486420423771700205474433798894�197\
>>> 466121469968970652154300626260453589099812575227594260877217437610731421774�923\
>>> 304821790494440983623823577230674987439676046337648021513346133347839568274�660\
>>> 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
>>
>
> Python has such a nice syntax and large integer math package!
>
> Here is a curious example.
>
> prime = 1299853
>
> The next prime that is 3 mod 4 from this one is
>
> next_prime_3_mod_4 = 1299887 (it is only 34 away)
>
> Trying to Add 4 to prime, testing for primality, and looping until
> successful seems to miss this one.
>
> What am I missing?

If both are 3 mod 4, their difference is 0 mod 4.
34 is not.
The problem is 1299853 = 1 mod 4. (52 = 13*4 :-))


I have another question: are your primes really primes,
or just "pseudoprimes" ? I mean, do you use only
a probabilistic algorithm ? Even if they are quite
good, it hurts me a little bit to say they are primes :-)
From: Mensanator on 29 Aug 2008 16:41
On Aug 29, 3:28 pm, amzoti <amz...(a)gmail.com> wrote:
> On Aug 28, 3:38 pm, Mensanator <mensana...(a)aol.com> wrote:
>
>
>
>
>
> > On Aug 28, 4:58 pm, amzoti <amz...(a)gmail.com> wrote:
>
> > > Hi,
>
> > > I have this prime (base 10):
>
> > > 104438888141315250667960271984652954583126906099213500902258875644433817202­­232\
> > > 269071044404666980978393011158573789036269186012707927049545451721867301692­­842\
> > > 745914600186688577976298222932119236830334623520436805101030915567415569746­­034\
> > > 717694639407653515728499489528482163370092181171673897245183497945589701030­­633\
> > > 346859075135836513878225037226911796898519432244453568741552200715163863814­­145\
> > > 617842062127782267499502799027867345862954439173691976629900551150544617766­­815\
> > > 444623488266596168079657690319911608934763494718777890652800800475669257166­­692\
> > > 296412256617458277670733245237100127216377684122931832490312574071357414100­­512\
> > > 456196591388889975346173534797001169325631675166067895083002751025580484610­­558\
> > > 346505544661509044430958305077580850929704003968005743534225392656624089819­­586\
> > > 363158888893636412992005930845566945403401039147823878418988859467233624276­­379\
> > > 513817635322284552464404009425896243361335403610464388192523848922401019419­­308\
> > > 891166616558422942466816544168892779046060826486420423771700205474433798894­­197\
> > > 466121469968970652154300626260453589099812575227594260877217437610731421774­­923\
> > > 304821790494440983623823577230674987439676046337648021513346133347839568274­­660\
> > > 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
>
> Python has such a nice syntax and large integer math package!
>
> Here is a curious example.
>
> prime = 1299853
>
> The next prime that is 3 mod 4 from this one is
>
> next_prime_3_mod_4 = 1299887 (it is only 34 away)
>
> Trying to Add 4 to prime, testing for primality, and looping until
> successful seems to miss this one.

Because this algorithm (by adding 4) only steps through
numbers that are the same congruence class mod 4 as 1299853.

>>> prime = 1299853
>>> prime % 4
1

>
> What am I missing?

The premise that 1299853 is congruence class 3 is false.

>
> Thanks
>
> ~A
> What am I missing - probably something stupid?

From: amzoti on 29 Aug 2008 16:41
On Aug 29, 1:35 pm, Jean-Claude Arbaut <jeanclaudearb...(a)orange.fr>
wrote:
> amzoti wrote:
> > On Aug 28, 3:38 pm, Mensanator <mensana...(a)aol.com> wrote:
> >> On Aug 28, 4:58 pm, amzoti <amz...(a)gmail.com> wrote:
>
> >>> Hi,
> >>> I have this prime (base 10):
> >>> 104438888141315250667960271984652954583126906099213500902258875644433817202­232\
> >>> 269071044404666980978393011158573789036269186012707927049545451721867301692­842\
> >>> 745914600186688577976298222932119236830334623520436805101030915567415569746­034\
> >>> 717694639407653515728499489528482163370092181171673897245183497945589701030­633\
> >>> 346859075135836513878225037226911796898519432244453568741552200715163863814­145\
> >>> 617842062127782267499502799027867345862954439173691976629900551150544617766­815\
> >>> 444623488266596168079657690319911608934763494718777890652800800475669257166­692\
> >>> 296412256617458277670733245237100127216377684122931832490312574071357414100­512\
> >>> 456196591388889975346173534797001169325631675166067895083002751025580484610­558\
> >>> 346505544661509044430958305077580850929704003968005743534225392656624089819­586\
> >>> 363158888893636412992005930845566945403401039147823878418988859467233624276­379\
> >>> 513817635322284552464404009425896243361335403610464388192523848922401019419­308\
> >>> 891166616558422942466816544168892779046060826486420423771700205474433798894­197\
> >>> 466121469968970652154300626260453589099812575227594260877217437610731421774­923\
> >>> 304821790494440983623823577230674987439676046337648021513346133347839568274­660\
> >>> 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
>
> > Python has such a nice syntax and large integer math package!
>
> > Here is a curious example.
>
> > prime = 1299853
>
> > The next prime that is 3 mod 4 from this one is
>
> > next_prime_3_mod_4 = 1299887 (it is only 34 away)
>
> > Trying to Add 4 to prime, testing for primality, and looping until
> > successful seems to miss this one.
>
> > What am I missing?
>
> If both are 3 mod 4, their difference is 0 mod 4.
> 34 is not.
> The problem is 1299853 = 1 mod 4. (52 = 13*4 :-))
>
> I have another question: are your primes really primes,
> or just "pseudoprimes" ? I mean, do you use only
> a probabilistic algorithm ? Even if they are quite
> good, it hurts me a little bit to say they are primes :-)

Dang!

I've been looking at numbers too long this week!

Thanks to you and Gordon for curing my stupidity!

~A
First  |  Prev  |  Next  |  Last
Pages: 1 2 3 4 5 6 7 8 9 10 11
Prev: Adi Shamir's Cube Attacks
Next: Merry Christmas 7