# RSA and Wiener's attack [closed]

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?

• 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. May 24, 2021 at 15:22
• 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$.
– j.p.
May 25, 2021 at 6:25
• @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. May 25, 2021 at 10:10
• I’m voting to close this question because this is about an error on SageMath and need to be asked at ask.sagamath.org May 25, 2021 at 10:11

"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)

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.)