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

```

• Prev by Date: Re: RE: Finding a relative prime
• Next by Date: Re: Re: Finding a relative prime (corrected)
• Previous by thread: Re: RE: Finding a relative prime
• Next by thread: Re: Re: Finding a relative prime