Re: RE: Finding a relative prime
- To: mathgroup at smc.vnet.net
- Subject: [mg19729] Re: [mg19694] RE: [mg19682] Finding a relative prime
- From: "Andrzej Kozlowski" <andrzej at tuins.ac.jp>
- Date: Mon, 13 Sep 1999 02:40:59 -0400
- Sender: owner-wri-mathgroup at wolfram.com
Here is my new attempt to answer my question (below). The solution is pretty
rough and I have some doubts about it, but I am giving it anyway because it
seems to me that it raises some interesting issues. Anyway, here is a
re-statement of the problem:
Problem: Find a "fast" deterministic program which, for a given prime q,
gives a random number between 2 and q-1 relatively prime to q so that each
such number is obtained with equal probability. The meaning of deterministic
is that for any given input there should be a finite time T such that the
program is certain to give an answer in time less than T.
There seems to be an obvious algorithm but it has not been clear (to me) how
to implement it easily in Mathematica. Namely, we choose a random number
between 2 and q-2. If it is relatively prime to q-1 we are done. If not, we
make another random choice but different from the one we just made. The
problem is how to implement this last condition.
The main point of the program below is to define a new function
random[{i,j},l], where i<j are integers and l a list of integers lying
between i and j, such that random[{i,j},l] is a random integer between i and
j but not in l. This should be done without constructing Range[i,j]
otherwise the program is no longer "fast".
In[1]:=
miss[k_][i_] /; i < k := i;
miss[k_][i_] /;i >= k := i + 1;
random[{i_, j_}, {}] := Random[Integer, {i, j}];
random[{i_, j_}, l_List] := miss[Last[l]][random[{i, j - 1}, Drop[l, -1]]];
This seems to work as it should. For example here is a list of uniformly
pseudo-random numbers between 1 and 9 not containing 3 and 5:
In[2]:=
Table[random[{1, 9}, {3, 5}], {20}]
Out[2]=
{1, 8, 7, 2, 9, 7, 1, 4, 8, 8, 6, 4, 7, 4, 4, 6, 8, 7, 2, 7}
Now the program PickNumber is:
PickNumber[q_?PrimeQ] :=
Module[{k = Random[Integer, {2, q - 2}], r = {}},
While[GCD[k, q - 1] (I-(J 1, AppendTo[r, k]; k = random[{2, q - 2}, r]]; k]
This seems to work with two reservations. First, it is noticeably slower
than the probabilistic programs, though much faster than my original
deterministic one. In any case I am sure it can be optimized to run much
faster. What is more worrying is that large number of runs of PickNumber[13]
show that 11 is somewhat less likely to be chosen than 5 or 7. I can't at
the moment see why this should be so. Can anyone explain this?
--
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: "Andrzej Kozlowski" <andrzej at tuins.ac.jp>, "Ersek, Ted R"
<ErsekTR at navair.navy.mil>, mathgroup at smc.vnet.net,timur at tabi.org
>Subject: [mg19729] Re: [mg19694] RE: [mg19682] Finding a relative prime
>Date: Sun, Sep 12, 1999, 8:47 PM
>
> 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 imput 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 betwen 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: [mg19729] 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: [mg19729] [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
>>>