What is the next Prime that is 3 mod 4 from this one? [Cryptography]

Prev: Adi Shamir's Cube Attacks
Next: Merry Christmas 7

From: Dave Seaman on 31 Aug 2008 13:12

On Sun, 31 Aug 2008 16:12:17 GMT, Unruh wrote:
> Dave Seaman <dseaman(a)no.such.host> writes:

>>On Sat, 30 Aug 2008 20:28:08 +0200, Boon wrote:
>>> Phil Carmody wrote:

>>>> Boon wrote:

>>>>> Phil Carmody wrote:

>>>>>> Are primes "odd with probability 1"?

>>>>> Given a random prime number greater than 2, I'd say it is odd with
>>>>> probability 1, yes. Would that be wrong?

>>>> Don't change the question - who said anything about 'greater than 2'?

>>> Meh. Given that there are infinitely many primes numbers and only one
>>> even prime number, then, if I remember the terminology correctly, we can
>>> say the a random pri�e number is odd "almost surely" (i.e. with
>>> probability 1).

>>> http://en.wikipedia.org/wiki/Almost_everywhere

>>You didn't specify a probability distribution on the primes. There is no such
>>thing as a uniform probability distribution on a countably infinite set, and
>>therefore you must have in mind some nonuniform probability distribution.
>>Which one is it?

>>>> If you want a different question, are primes greater than 2 with
>>>> probability 1?

>>> As a matter of fact, yes :-)

>>> The set of primes not greater than 2 is a null set.

>>> http://en.wikipedia.org/wiki/Null_set

>>Same objection applies. It cannot be the case that each prime has probability
>>zero, since probability is countably additive and the sum over all primes is
>>required to be 1.

> Sure it can. The infinite sum of zeros can be whatever you want. If you
> want formal limits.

An uncountable sum of zeros can be whatever you want, as in measure
theory. However, this is a countable sum of zeros, and probability
measures are countably additive.

> given a cutoff N, the number of primes is something like N/ln(N), so the
> probability of any particular prime is ln(N)/N. As N goes to infinity, this
> goes to zero. Ie the limiting probability is 0. But the limit of th esum is
> 1.

If you wanted to talk about densities instead of probabilities, why
didn't you just say so in the first place? It's not the same.

--
Dave Seaman
Third Circuit ignores precedent in Mumia Abu-Jamal ruling.
<http://www.indybay.org/newsitems/2008/03/29/18489281.php>

From: Jean-Claude Arbaut on 31 Aug 2008 13:16

Unruh wrote:

> Sure it can. The infinite sum of zeros can be whatever you want. If you
> want formal limits.
> given a cutoff N, the number of primes is something like N/ln(N), so the
> probability of any particular prime is ln(N)/N.

Do you know what a probability distribution is ?

> As N goes to infinity, this
> goes to zero. Ie the limiting probability is 0. But the limit of th esum is
> 1.
>
>

From: Pubkeybreaker on 1 Sep 2008 18:45

On Aug 29, 4: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 :-)- Hide quoted text -
>
> - Show quoted text -

You are misusing the term 'pseudoprime'. A pseudoprime
is composite. You mean "probable prime"

From: Pubkeybreaker on 1 Sep 2008 18:47

On Aug 29, 4:44ï¿½pm, amzoti <amz...(a)gmail.com> wrote:
> 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?

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

You are misusing the word 'pseudoprime'. A pseudoprime is
composite. You mean 'probable prime'.

From: Pubkeybreaker on 1 Sep 2008 18:48

On Aug 29, 5:34ï¿½pm, Jean-Claude Arbaut <jeanclaudearb...(a)orange.fr>
wrote:
> 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:

> 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

AKS is horribly slow. And I guarantee that you don't want
'pseudoprime' tests.

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