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 29 Aug 2008 16:44 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): > >>> 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 > > > 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 :-) I would probably call them pseudoprimes as they are passing 1) first tests for divisibility using small primes 2) then Miller - Rabin strong pseudoprime test base 2 and base 3 3) and then uses a Lucas test. But you are correct - if we wanted to be more exacting - we would not call these prime. ~A
From: Mensanator on 29 Aug 2008 16:56 On Aug 29, 3: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): > >>> 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 > > > 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" ? Shh...ix-nay on the eudoprimes-psay. > I mean, do you use only a probabilistic algorithm ? That's what gmpy uses: 0 means composite, 1 means probably prime and 2 means definitely prime. The Python statement if gmpy.is_prime(n) is true for all non-0 results. > Even if they are quite > good, it hurts me a little bit Well, you can add some bits to the probability calculation. Help on built-in function is_prime in module gmpy: is_prime(...) is_prime(x,n=25): returns 2 if x is _certainly_ prime, 1 if x is _probably_ prime (probability > 1 - 1/2**n), 0 if x is composite. If x<0, GMP considers x 'prime' iff -x is prime; gmpy reflects this GMP design choice. x must be an mpz, or else gets coerced to one. > to say they are primes :-) I won't say anything if you don't.
From: Jean-Claude Arbaut on 29 Aug 2008 17:34 Mensanator wrote: > On Aug 29, 3: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" ? > > Shh...ix-nay on the eudoprimes-psay. > >> I mean, do you use only a probabilistic algorithm ? > > That's what gmpy uses: 0 means composite, 1 means probably > prime and 2 means definitely prime. The Python statement > > if gmpy.is_prime(n) > > is true for all non-0 results. > >> Even if they are quite >> good, it hurts me a little bit > > Well, you can add some bits to the probability calculation. > > Help on built-in function is_prime in module gmpy: > > is_prime(...) > is_prime(x,n=25): returns 2 if x is _certainly_ prime, 1 if x is > _probably_ prime (probability > 1 - 1/2**n), 0 if x is composite. > If x<0, GMP considers x 'prime' iff -x is prime; gmpy reflects > this > GMP design choice. x must be an mpz, or else gets coerced to one. > > >> to say they are primes :-) > > I won't say anything if you don't. > Actually, I would have been interested by an implementation of the Agrawal-Kayal-Saxena algorithm in python ;-) But depending on applications, it may be enough to have pseudoprime tests.
From: Thomas Pornin on 29 Aug 2008 18:04 According to Mensanator <mensanator(a)aol.com>: > Well, you can add some bits to the probability calculation. > > Help on built-in function is_prime in module gmpy: > > is_prime(...) > is_prime(x,n=25): returns 2 if x is _certainly_ prime, 1 if x is > _probably_ prime (probability > 1 - 1/2**n), 0 if x is composite. > If x<0, GMP considers x 'prime' iff -x is prime; gmpy reflects > this > GMP design choice. x must be an mpz, or else gets coerced to one. Note that there is no such thing as a "probably prime integer". The integer is prime, or not. What we want to express is that we do not know with 100% certainty the actual status of that integer. However, 100% certainty is quite moot. What we need, for the purpose of communicating through Usenet messages, is a risk of failure no greater than the risk of a message being modified by a freak transmission error. Consider, for instance, the probability that a message which shows on your screen as "this integer is prime" becomes, when sent on the wire, "this integer is not prime". That probability is small but not zero. Random bit flips and their consequences are rare but they do occur (I have seen several myself). What this amounts to is that if is_prime(x, 100) returns a non-zero result, then the integer is known to be prime with quite enough certainty and it makes no sense to elaborate more on the subject. Or, in other words: if stating that an integer is prime, whereas it has only been tested up to a certainty of 1-(1/2)^100, is a painfull thing, then stating _anything_ mathematical in a Usenet message must hurt quite a bit. And, if not, then surely somebody is getting his priorities wrong. The documentation above, however, seems to imply that the default value for n is 25, which means that a composite number may have a probability of up to 1 in about 30 millions to be declared prime. This is a bit high for my comfort. --Thomas Pornin
From: Jean-Claude Arbaut on 29 Aug 2008 18:20
Thomas Pornin wrote: > According to Mensanator <mensanator(a)aol.com>: >> Well, you can add some bits to the probability calculation. >> >> Help on built-in function is_prime in module gmpy: >> >> is_prime(...) >> is_prime(x,n=25): returns 2 if x is _certainly_ prime, 1 if x is >> _probably_ prime (probability > 1 - 1/2**n), 0 if x is composite. >> If x<0, GMP considers x 'prime' iff -x is prime; gmpy reflects >> this >> GMP design choice. x must be an mpz, or else gets coerced to one. > > Note that there is no such thing as a "probably prime integer". The > integer is prime, or not. What we want to express is that we do not know > with 100% certainty the actual status of that integer. Some would view this as a probability : a measure of uncertainty. > However, 100% > certainty is quite moot. > What we need, for the purpose of communicating > through Usenet messages, is a risk of failure no greater than the risk > of a message being modified by a freak transmission error. In such a case it's not too important. But in some cases you say a number is a prime and you need to be absolutely sure. > Consider, for > instance, the probability that a message which shows on your screen as > "this integer is prime" becomes, when sent on the wire, "this integer is > not prime". That probability is small but not zero. Random bit flips and > their consequences are rare but they do occur (I have seen several > myself). What this amounts to is that if is_prime(x, 100) returns a > non-zero result, then the integer is known to be prime with quite enough > certainty and it makes no sense to elaborate more on the subject. It's not a _prime_. > Or, in other words: if stating that an integer is prime, whereas it has > only been tested up to a certainty of 1-(1/2)^100, is a painfull thing, > then stating _anything_ mathematical in a Usenet message must hurt quite > a bit. And, if not, then surely somebody is getting his priorities > wrong. I don't think so. > The documentation above, however, seems to imply that the default value > for n is 25, which means that a composite number may have a probability > of up to 1 in about 30 millions to be declared prime. This is a bit high > for my comfort. For me, even the slightest risk should not be acceptable from the mathematical point of vue. If you don't need certainty in applications, perfect. But don't call it a prime. Or you might as well say 1.00000000000000000000000000001 is an integer. |