Search code examples
cryptographymodulosagelargenumber

SageMath: Mod().sqrt() prefixed with "sqrt" string for a particular combination in Sagemath. Is this a bug?


Using Sagemath 9.2 on Windows 10

a1 = 9798722381116618056227637476565566484018606253194222755351973203508462742253522311154076194134700145275527578605535821781545038187843569198505993524407287520970070771172279404172004212310432500247465608472105231701909612623072343883942216806934904529600639676698348239426243771486521532222069409611514728756060897629936844695006373653175992634673678639333010508845045985607328371180356262460490393317997708599757357055386370808544031455931154122353547239678217006604692623467390849309525705453042722141078914816760002281629323554959490483823338710209710265138177331357093216148991708169324688688552846634664517554736

n = 27772857409875257529415990911214211975844307184430241451899407838750503024323367895540981606586709985980003435082116995888017731426634845808624796292507989171497629109450825818587383112280639037484593490692935998202437639626747133650990603333094513531505209954273004473567193235535061942991750932725808679249964667090723480397916715320876867803719301313440005075056481203859010490836599717523664197112053206745235908610484907715210436413015546671034478367679465233737115549451849810421017181842615880836253875862101545582922437858358265964489786463923280312860843031914516061327752183283528015684588796400861331354873

a2 = Mod(a1, n).sqrt()

I get the following

sage: print(a2) sqrt9798722381116618056227637476565566484018606253194222755351973203508462742253522311154076194134700145275527578605535821781545038187843569198505993524407287520970070771172279404172004212310432500247465608472105231701909612623072343883942216806934904529600639676698348239426243771486521532222069409611514728756060897629936844695006373653175992634673678639333010508845045985607328371180356262460490393317997708599757357055386370808544031455931154122353547239678217006604692623467390849309525705453042722141078914816760002281629323554959490483823338710209710265138177331357093216148991708169324688688552846634664517554736

If you observe, a2 is prefixed with sqrt!

I don't see this with other roots, I calculated with Sage. What does this mean?

Is this a bug or does this have some other meaning?


Solution

  • It would appear n is prime (at least pseudo-prime):

    sage: n.is_prime(proof=False)
    True
    

    Assuming it is, let us define the finite field in n elements:

    sage: F = GF(n, proof=False)
    

    and view a1 as an element A1 in F:

    sage: A1 = F(a1)
    

    Asking whether a1 is a square modulo n amounts to asking whether A1 a square in F.

    sage: A1.is_square()
    False
    

    It is not! So when we compute the square root of A1, it has to be in a quadratic extension of F.

    This is why when we ask Sage to compute this square root, it gives it as a generator of that extension.

    A natural name for this generator is "sqrt(n)", which is what Sage uses.

    Probably, when you computed other square roots, they were square roots of numbers which were squares modulo n, and therefore the square roots could be computed in F, i.e. in ZZ / n ZZ, without requiring a quadratic field extension.