TransWikia.com

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

Mathematica Asked on February 23, 2021

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

  1. $au-bv=1$ (Euclidean algorithm)

  2. $au+bv$ is a prime

  3. $GCD(ab,uv)=1$

  4. $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.

One 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} *)

Correct answer by Daniel Lichtblau on February 23, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP