Re: RE: Finding a relative prime
- To: mathgroup at smc.vnet.net
- Subject: [mg19725] Re: [mg19694] RE: [mg19682] Finding a relative prime
- From: "Andrzej Kozlowski" <andrzej at tuins.ac.jp>
- Date: Mon, 13 Sep 1999 02:40:57 -0400
- Sender: owner-wri-mathgroup at wolfram.com
Unfortunately there several bad mistakes in the algorithm of my PicNumber2
below. The easiest way to "fix" it is:
PickNumber2[q_, r_:2] := If[GCD[k = Random[Integer, {r, q - 2}], q - 1] ==
1, k, PickNumber2[q, k + 1]]
This does choose randomly a number between 2 and q-1 which is relatively
prime to q-1, but not all such numbers are chosen with equal probability.
For example if q=13 then 11 is much more likely to be chosen that 5 or 7. In
general q-2, which is always relatively prime to q-1, will always be the
most likely number to be chosen by this algorithm.
In any case, a "probabilistic" algorithm is perfectly satisfactory here. In
number theory a number of fast probabilistic algorithms are known. They
depend on a random choice being made at some point and if the choice turns
out to be a bad one the algorithm goes back and makes another choice. Such
an algorithm has the property that for any given input and any finite time T
there is a finite probability greater than zero that the algorithm will not
stop in time T. Both Ted's algorithm and my PickNumber1 are of this kind. My
original program was not probabilistic but much less efficient because it
checked all numbers between 2 and q-2 .
I do not know if a fast deterministic algorithm which gives all answers with
equal probability can be produced in this case (again, by deterministic I
mean here one that for any given input is guaranteed to stop in a finite
time). If any one can answer this or produce an example I would be
interested to see it.
--
Andrzej Kozlowski
Toyama International University
JAPAN
http://sigma.tuins.ac.jp
http://eri2.tuins.ac.jp
----------
>From: "Andrzej Kozlowski" <andrzej at tuins.ac.jp>
To: mathgroup at smc.vnet.net
>To: "Ersek, Ted R" <ErsekTR at navair.navy.mil>,
mathgroup at smc.vnet.net,timur at tabi.org
>Subject: [mg19725] Re: [mg19694] RE: [mg19682] Finding a relative prime
>Date: Sun, Sep 12, 1999, 6:31 PM
>
> 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 very long (or not stopping) but in practice will be
> vastly faster than the one I gave, which requires finding all the numbers
> beween 2 and q which are relatively prime to q. (I still tend to think
> like a pure mathematician and often 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 relativley
> 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. The advantage of this second approach is that it will never select the
> same number twice, One can see the difference between them by evaluating
> Trace[PickNumberi[13]] a few times, though in practice this gain in
> efficinecy 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: [mg19725] [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
>>