MathGroup Archive 1999

[Date Index] [Thread Index] [Author Index]

Search the Archive

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


  • Prev by Date: Re: RealTime3D in v4.0: Capabilities and compatibilities
  • Next by Date: Re: Langford's Problem (yet another improvement!)
  • Previous by thread: Re: Finding a relative prime
  • Next by thread: Re: Finding a relative prime