Re: RE: Finding a relative prime

*To*: mathgroup at smc.vnet.net*Subject*: [mg19724] Re: [mg19694] RE: [mg19682] Finding a relative prime*From*: "Andrzej Kozlowski" <andrzej at tuins.ac.jp>*Date*: Mon, 13 Sep 1999 02:40:56 -0400*Sender*: owner-wri-mathgroup at wolfram.com

Comparing Ted's solution (below) with mine I remembered something which I had quite forgotten when answering this question: namely that in programs of this kind one can gain a lot of speed by adopting a "probabilistic" approach. Ted's solution is of course of this kind. It has a very small chance of taking a very long time (or not stopping) but in practice will be vastly faster than the one I gave, which requires finding all the numbers between 2 and q which are relatively prime to q. (I still tend to think like an old fashioned mathematician from pre-computer days and forget to consider the speed of my programs). Perhaps a slightly more elegant version of Ted's program is PickNumber1[q_?PrimeQ] := If[GCD[k = Random[Integer, {2, q - 1}], q-1] == 1, k, PickNumber1[q]] If one really wanted to guarantee that the algorithm will never unluckily "stall" by repeatedly selecting the same numbers numbers not relatively prime to q-1 (e.g 2,4,6,4,6,2,3,... for q=13) we can use a slightly more complicated one, e.g. PickNumber2[q_, r_:2] := Which[GCD[k = Random[Integer, {r, q - 1}], q - 1] == 1, k, k == r, PickNumber2[q, k + 1], Random[Integer] == 0, PickNumber2[r, k - 1], True, PickNumber2[q, k + 1]] What PrimeNumber2[q] does is this: it picks a number k at random from Range[2,q-1] and tests if it is relatively prime to q-1. If yes it returns this number, if not it chooses a random number between 2 and q-1 other than k. Thus the advantage of this approach is that it will never select the same number twice, One can see the difference by evaluating Trace[PickNumberi[13]] for i=1 and 2 a few times, though in practice this gain in efficiency is unlikely to be significant. Andrzej Kozlowski Toyama International University JAPAN http://sigma.tuins.ac.jp http://eri2.tuins.ac.jp ---------- >From: "Ersek, Ted R" <ErsekTR at navair.navy.mil> To: mathgroup at smc.vnet.net >To: mathgroup at smc.vnet.net >Subject: [mg19724] [mg19694] RE: [mg19682] Finding a relative prime >Date: Sun, Sep 12, 1999, 5:36 AM > > Timur Tabi wrote: > ------------------------ > 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, > 2) k is relatively prime to p-1. > > ------------------------ > > This should work: > > > PickNumber[p_?PrimeQ]:= > Module[{tst,k}, > While[tst=!=1, > k=Random[Integer,{2,p-2}]; > tst=GCD[k,p-1] > ]; > k > ] > > > However, when p=2,3,5,7 > there is only one integer less than (p-1) > that is relatively prime to (p-1), and that doesn't > allow for a very random outcome. > > -------------------- > Regards, > Ted Ersek > > For Mathematica tips, tricks see > http://www.dot.net.au/~elisha/ersek/Tricks.html >