0

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.

Malik Hamza Murtaza
  • 85
  • I don't understand this question. You're looking for integers $N$ whose inverses have what properties exactly...? – Myridium Dec 28 '17 at 08:31
  • 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. – Malik Hamza Murtaza Dec 28 '17 at 10:59
  • 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. – Myridium Dec 28 '17 at 11:24
  • 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! – Myridium Dec 28 '17 at 11:30
  • @Myridium compared to long division. – Malik Hamza Murtaza Dec 29 '17 at 20:10

2 Answers2

1

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.

Arthur
  • 199,419
1

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

Zubair Iqbal
  • 26
  • 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 :( – Malik Hamza Murtaza Dec 29 '17 at 22:12