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
>