0
$\begingroup$

I have been trying to find inverses of large integers (could be upto 2048 bits), such that 1/N has a minimal period p and n its length in binary. (what i actually am interested in finding is the length of the minimal period n)

Now could someone suggest a faster method of either obtaining the inverse upto a precision that's greater than n or some other method of finding n that doesn't take ages to compute...

Further restrictions on N are that it will always be a semi prime number. however the factors are unknown and factorization would take a lot of time thereby gets infeasible.

$\endgroup$
  • $\begingroup$ I don't understand this question. You're looking for integers $N$ whose inverses have what properties exactly...? $\endgroup$ – Myridium Dec 28 '17 at 8:31
  • $\begingroup$ i need to find the inverses of integers in a feasible time, with an accuracy atleast equal to the length of the minimal period of the inverse. or in other words i need to know the exact length of the minimal period of the inverse on an integer. the integer will always be a semiprime, with unknown factors. $\endgroup$ – Malik Hamza Murtaza Dec 28 '17 at 10:59
  • $\begingroup$ I'm sorry but this question really doesn't make sense. You're trying to find an integer $N$ that has a minimal period $p$. Okay... what is the minimal period? $n$ its length in binary? If we're talking about a period, presumably we're talking about a decimal representation i.e. $0.3333333\dots$ which has infinite length, even in base $2$. If this is a computation problem, you should ask it on CSSE. $\endgroup$ – Myridium Dec 28 '17 at 11:24
  • $\begingroup$ I have been computing the inverses of integers $N$ up to 2048 bits. For each of these integers, I find the minimal period of its decimal expansion, and encode that period $p$ into binary. The length of this binary representation of $p$, call it $n$, is what I'm ultimately trying to compute for each integer $N$. - is this what you mean?? If so, you ask for a "faster" method. Faster than what? You haven't shown a method! $\endgroup$ – Myridium Dec 28 '17 at 11:30
  • $\begingroup$ @Myridium compared to long division. $\endgroup$ – Malik Hamza Murtaza Dec 29 '17 at 20:10
1
$\begingroup$

Use Newton's method to divide quickly. https://en.wikipedia.org/wiki/Newton%27s_method and watch this video https://www.youtube.com/watch?v=AoVI9NWegWw

$\endgroup$
  • $\begingroup$ Actually i did apply newton raphson's division, it kinda improved the issue, while getting me stuck with other issues creating instances of huge numbers i.e.numbers with a few million digits. will get back to you once i sort it out a bit :( $\endgroup$ – Malik Hamza Murtaza Dec 29 '17 at 22:12
1
$\begingroup$

I asked a more general version of this question a while ago, and going by the answer I got, to get the length of the minimal period you first factor out all factors $2$ from $N$ to get $N'$ (which is feasible, especially in binary).

The answer is then equal to the multiplicative order of $2$ modulo $N'$. Whether there is a good algorithm for this, I don't know, but it's such a common problem that someone ought to have thought of something clever.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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