0
$\begingroup$

I'm trying to do Wieners' attack for the case \

n = 41812289888807017163984918063150535143241733968369526096686035411100281058895684734892837916893307091448099221185297849468517662339430579635277837641016589091836673752854703947923396020640786536145707 
c = 5647541533380963346585224364224434677403723951263986948810198754525250531609090519481526140311081703727277595838311994257275863156449937037100899820505224056792266899834932182748239916430052642900127.

I'm using SageMath and I computed the continued fraction of $n/c$ and the first 10 convergents ($p_n/q_n$). Now I'm trying to see if $a^{cq_i} \equiv a \pmod{n}$. It happens that Sage says that the exponent is too high and PARI online said the said. Can I make these computations an easier way?

Improve this question
$\endgroup$
4
  • 2
    $\begingroup$ If you have a problem with SageMath, there is ask.sagemath.org/questions for this type of question. Also, you can implement your binary modular exponentiation. Or, you can use GNU/MP. $\endgroup$
    – kelalaka
    May 24, 2021 at 15:22
  • 2
    $\begingroup$ The problem you have with the exponent being too high is caused by calculating first the exponent (resulting in a giant number) and then reducing modulo $n$. The reduction should be done during the exponentiation, not afterwards. In python you can use pow(b, e, m) for calculating $b^e\bmod m$. $\endgroup$
    – j.p.
    May 25, 2021 at 6:25
  • $\begingroup$ @j.p. actually, I've tested with SageMath that can handle the very big exponenets, too. I don't see a reason. Better to be asked at ask.sagemath.org with the code. $\endgroup$
    – kelalaka
    May 25, 2021 at 10:10
  • 3
    $\begingroup$ I’m voting to close this question because this is about an error on SageMath and need to be asked at ask.sagamath.org $\endgroup$
    – kelalaka
    May 25, 2021 at 10:11

1 Answer 1

Reset to default
1
$\begingroup$

"Too big" in modular exponentiation means that you're trying to exponentiate-then-modulo, which creates huge intermediate numbers; that isn't how you're supposed to do modular-root-based cryptography. You should use SageMath's IntegerModRing to work inside such groups, instead of "manually" running a modulo operation on attempted exponentiation results.

sage: R = IntegerModRing(n)
sage: a = R(a)
sage: assert a^(c*q[i])  == a

Dedicated modular-exponentiation systems will internally "cheat" by keeping numbers pruned to a manageable size throughout the process (generally with a technique like Montgomery reduction) so they never have to handle "exponentially large" numbers.

Or, if you're just aiming at a "quick and dirty" calculation, you could use power_mod (cf. Python's pow, OpenSSL's BN_mod_mul, etc.)

Improve this answer
$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.