Re: Re: Finding a relative prime

*To*: mathgroup at smc.vnet.net*Subject*: [mg19727] Re: [mg19704] Re: Finding a relative prime*From*: Ken Levasseur <Kenneth_Levasseur at uml.edu>*Date*: Mon, 13 Sep 1999 02:40:58 -0400*Organization*: UMass Lowell Mathematical Sciences*References*: <7r7kal$ckp@smc.vnet.net> <199909112036.QAA04455@smc.vnet.net.>*Sender*: owner-wri-mathgroup at wolfram.com

Choosing from just the primes isn't general enough; but even if it were,for cryptographic purposes generating all of the relative primes or primes less than p-1 wouldn't be practical. Since the ratio EulerPhi[p-1]/(p-1) is always fairly large (I don't think it goes below 0.2 for numbers that would be considered here the most efficient approach is to test random integers between 2 and p-1 until one of them is rel. prime to p-1 like this: relprime[p_] := FixedPoint[Random[Integer, {2, p - 2}] &, p - 1, SameTest -> ((GCD[p - 1, #2] == 1) &)] Ken Levasseur UMass Lowell Shazam wrote: > > Can't you just pick any random prime q between 2 and p-1 and then q and p-1 > are automatically relatively prime? Or do you need to consider any > relatively prime number as potential numbers to pick? > > I think I would know how to do the above but I would have to look it up > (last semester I took a cryptography course and we did things like > that)..... > > If you can't figure it out then let me know and I'll look it up....... > > Timur Tabi <nospam_timur at tabi.org> wrote in message > news:7r7kal$ckp at smc.vnet.net... > > I'm using Mathematica 3.0 for the Mac, and I'm trying to figure out how > > to get it to pick a random number that is relatively prime to another > > number, p-1, where p is prime. In other words, pick a random number k > > such that 1) k is between 2 and p-1, and 2) k is relatively prime to p-1. > > How can I do that in Mathematica 3.0? > > > > -- > > Remove "nospam_" from my email address when replying > > Timur "too sexy for my code" Tabi, timur at tabi.org > > > > > > Sent via Deja.com http://www.deja.com/ > > Share what you know. Learn what you don't. > >

**References**:**Re: Finding a relative prime***From:*"Shazam" <gmon@toad.net>