How to resolve the algorithm Tonelli-Shanks algorithm step by step in the REXX programming language

Published on 12 May 2024 09:40 PM
#Rexx

How to resolve the algorithm Tonelli-Shanks algorithm step by step in the REXX programming language

Table of Contents

Problem Statement

In computational number theory, the Tonelli–Shanks algorithm is a technique for solving for x in a congruence of the form:

where n is an integer which is a quadratic residue (mod p), p is an odd prime, and x,n ∈ Fp where Fp = {0, 1, ..., p - 1}. It is used in cryptography techniques.

To apply the algorithm, we need the Legendre symbol: The Legendre symbol (a | p) denotes the value of a(p-1)/2 (mod p).

All ≡ are taken to mean (mod p) unless stated otherwise.

Implement the above algorithm. Find solutions (if any) for

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Tonelli-Shanks algorithm step by step in the REXX programming language

Source code in the rexx programming language

/* REXX (required by some interpreters) */
Numeric Digits 1000000
ttest ='[(10, 13), (56, 101), (1030, 10009), (44402, 100049)]'
Do While pos('(',ttest)>0
  Parse Var ttest '(' n ',' p ')' ttest
  r = tonelli(n, p)
  Say "n =" n "p =" p
  Say "          roots :" r (p - r)
  End
Exit

legendre: Procedure
  Parse Arg a, p
  return pow(a, (p - 1) % 2, p)

tonelli: Procedure
  Parse Arg n, p
  q = p - 1
  s = 0
  Do while q // 2 == 0
    q = q % 2
    s = s+1
    End
  if s == 1 Then
    return pow(n, (p + 1) % 4, p)
  Do z=2 To p
    if p - 1 == legendre(z, p) Then
      Leave
    End
  c = pow(z, q, p)
  r = pow(n, (q + 1) / 2, p)
  t = pow(n, q, p)
  m = s
  t2 = 0
  Do while (t - 1) // p <> 0
    t2 = (t * t) // p
    Do i=1 To m
      if (t2 - 1) // p == 0 Then
        Leave
      t2 = (t2 * t2) // p
      End
    y=2**(m - i - 1)
    b = pow(c, y, p)
    If b=10008 Then Trace ?R
    r = (r * b) // p
    c = (b * b) // p
    t = (t * c) // p
    m = i
    End
  return r
pow: Procedure
  Parse Arg x,y,z
  If y>0 Then
    p=x**y
  Else p=x
  If z>'' Then
    p=p//z
  Return p

You may also check:How to resolve the algorithm Integer sequence step by step in the PILOT programming language
You may also check:How to resolve the algorithm Arbitrary-precision integers (included) step by step in the OCaml programming language
You may also check:How to resolve the algorithm Parsing/Shunting-yard algorithm step by step in the zkl programming language
You may also check:How to resolve the algorithm Abelian sandpile model step by step in the Mathematica/Wolfram Language programming language
You may also check:How to resolve the algorithm Rename a file step by step in the FutureBasic programming language