code: def _sqrt_mod_tonelli_shanks(a, p):
      """
      Returns the square root in the case of ``p`` prime with ``p == 1 (mod 8)``
  
      Assume that the root exists.
  
      Parameters
      ==========
  
      a : int
      p : int
          prime number. should be ``p % 8 == 1``
  
      Returns
      =======
  
      int : Generally, there are two roots, but only one is returned.
            Which one is returned is random.
  
      Examples
      ========
  
      >>> from sympy.ntheory.residue_ntheory import _sqrt_mod_tonelli_shanks
      >>> _sqrt_mod_tonelli_shanks(2, 17) in [6, 11]
      True
  
      References
      ==========
  
      .. [1] Carl Pomerance, Richard Crandall, Prime Numbers: A Computational Perspective,
             2nd Edition (2005), page 101, ISBN:978-0387252827
  
      """
      s = bit_scan1(p - 1)
      t = p >> s
      # find a non-quadratic residue
      if p % 12 == 5:
          # Legendre symbol (3/p) == -1 if p % 12 in [5, 7]
          d = 3
      elif p % 5 in [2, 3]:
          # Legendre symbol (5/p) == -1 if p % 5 in [2, 3]
          d = 5
      else:
          while 1:
              d = randint(6, p - 1)
              if jacobi(d, p) == -1:
                  break
      # assert legendre_symbol(d, p) == -1
      A = pow(a, t, p)
      D = pow(d, t, p)
      m = 0
      for i in range(s):
          adm = A * pow(D, m, p) % p
          adm = pow(adm, 2 ** (s - 1 - i), p)
          if adm % p == p - 1:
              m += 2**i
      # assert A*pow(D, m, p) % p == 1
      x = pow(a, (t + 1) // 2, p) * pow(D, m // 2, p) % p
      return x
  
imports: from __future__ import annotations
  from sympy.external.gmpy import gcd, lcm, invert, sqrt, legendre, jacobi, kronecker, bit_scan1, remove
  from sympy.polys import Poly
  from sympy.polys.domains import ZZ
  from sympy.polys.galoistools import gf_crt1, gf_crt2, linear_congruence, gf_csolve
  from .primetest import isprime
  from .factor_ import factorint, _perfect_power
  from .modular import crt
  from sympy.utilities.decorator import deprecated
  from sympy.utilities.memoization import recurrence_memo
  from sympy.utilities.misc import as_int
  from sympy.utilities.iterables import iproduct
  from sympy.core.random import _randint, randint
  from itertools import product
label_desc: Use image node_id 7 for calling a global function with example usage: _sqrt_mod_tonelli_shanks(a, p) and returns: x