How to write this simple task of unimodular prime search in mathematica?

Question

For testing a particular algorithm I found mathematica is the best way as it has all the tools I need. I am stuck in a number theory part and since I am not an expert in mathematica I do not know how to write a code that seemingly involves loops. I want to pick random integers $a,b$ in interval $[T,2T]$ at $T>0$ and obtain $u,vinmathbb Z$ such that

$au-bv=1$ (Euclidean algorithm)

$au+bv$ is a prime

$GCD(ab,uv)=1$

$0<u,v<4T$

holds.
Is there simple enough code to do this?
It would help me to have 5. $a,b,u,v$ are all prime integers.

Daniel Lichtblau · Accepted Answer

primeVectors[max_, tries_] := Catch[Module[
   {a, b, done = False, tt = 0, u, v, egcd},
   While[! done && tt < tries,
    tt++;
    {a, b} = RandomInteger[{2, max}, 2];
    egcd = ExtendedGCD[a, b];
    If[egcd[[1]] =!= 1, Continue[]];
    {u, v} = {1, -1}*egcd[[2]];
    If[u < 0,
     {u, v} = {u, v} + {b, -a}; If[u < 0, Continue[]]];
    If[(! PrimeQ[a*u + b*v] || GCD[a*b, u*v] =!= 1), Continue[], 
     Throw[{{a, b}, {u, v}}]]
    ];
   $Failed
   ]]

examples:
SeedRandom[1234]
Table[primeVectors[1000, 15], 10]

(* Out[2247]= {{{899, 664}, {243, 329}}, $Failed, {{544, 
   695}, {359, -807}}, $Failed, $Failed, {{215, 
   571}, {409, -276}}, {{79, 347}, {123, 28}}, {{313, 555}, {172, 
   97}}, {{581, 155}, {151, -596}}, {{395, 313}, {42, 53}}} 7} *)

How to write this simple task of unimodular prime search in mathematica?

One Answer

Add your own answers!

Ask a Question