[Tutor] MemoryError

[Satya Luzy]

Dear everyone, thank you for all of your support.
To Alan :
It is true that my code still need some improvement on the efficiency part,
and thanks for pointing out which part that needs to be improved. Speaking
of the nested loops, with my ability, I don't think I could simplify it, as
the nested loops is meant to look for a same value that occured twice or
more in the table (that's how the algorithm works, in my learning).
Really appreciate it :)

To Steven :
Well, I used a Laptop with i5 processor and 6GB of RAM in Windows 8 64-bit.
Wouldn't that be enough?
Either way, it is true that my method is not the best factorization method
nowadays. It was best used in the 70's. And I'm here to just do a research.
So it's not really surprising that it will not be that fast to have the
process done. I'm just having a problem because the process is interrupted
with MemoryError.

To Danny :
I'm sorry for the unfavored topic. Yeah I have understood the method and I
was just trying to convert it into code. By the way, I'm using the
references of (Mollin, Public Key Cryptography).

To Martin :
It is also true that I forgot to mention that the tested 10-digit numbers
are the non-prime numbers (Yeah, seems like I will have to add a primality
test before running the factorization). I was just too desperate to use the
global variable (lol). Yeah, I will try my best to avoid using it in the
future time. In my codes, the output of having 4 or more lines are to be
expected, for the first two lines are value of Q that is being compared due
to the same value and take the value associated with Q, which is A. Q is
printed and A is not. Then the last 2 lines are the actual factor. Thank
you for improving my code.


By the way, did a little bit of searching, does my 64-bit Operating System
has less performance because it is used for a 32-bit activity?

Really glad to have this community.
Have a good day!


On Wed, Dec 30, 2015 at 9:29 AM, Martin A. Brown <martin at linux-ip.net>
wrote:

>
> Hello there Satya,
>
> >I am currently working on a program to find the prime factor of n, in
> which
> >n is a big integer. Using the Continued Fraction factorization method (I
> >will provide the source code below, please don't mind the variables).
>
> I do not know the Continued Fraction factorization method.  (I admit
> to not looking it up and simply examining your code.)
>
> >It works perfectly when factorizing below 10 digits numbers.
>
> Are you certain?  All 10 digit numbers?  Or just the 10 digit
> numbers you tried?  I ask because....  Well, please see my second
> point below.
>
> >In my code below you will see on how I tried to factorize
> >94152743499601547, but get this message instead :
>
> Alan, Steven and Danny have other useful comments.  I will not
> repeat those.
>
> You may find it a bit easier to diagnose which data structure is
> exploding in size by logging/printing the contents of the lists p, Q
> and A, which you maintain in the function faktorisasi_default().
>
> I made a few small modifications to your code (see below) so that I
> could run it on smaller numbers.  Here are some comments:
>
>   * I adjusted the variables accepted in faktorisasi_default so that
>     there is no need for using a 'global' variable.  I don't like
>     using globals if it is possible to avoid.  In pure mathematical
>     functions, it is usually possible to avoid using a global.  If
>     you need an intermediate work product from the function (in
>     addition to the result), then simply return the intermediate
>     work product along with the result.
>
>   * See below my (slight) modifications to your code.  Now, you can
>     see how I'm running the program to perform some more diagnosis.
>     I think you have some sort of recursion termination problem in
>     your functions which are implementing your factoring.  In
>     short, determining I don't think that faktorisasi_default knows
>     when to stop.  Here's how I drew this conclusion:
>
>       python wuzzyluzy.py 18      # -- stops with four lines of output
>       python wuzzyluzy.py 12275   # -- stops with four lines of output
>       python wuzzyluzy.py 262144  # -- stops with many lines of output
>       python wuzzyluzy.py 17      # -- never stops
>       python wuzzyluzy.py 19      # -- never stops
>
> Good luck in your hunt for the wily factors,
>
> -Martin
>
>
>
> import fractions
> import math
>
> # CFRAC
> def cfract(n, boundary):
>    coeff = 1
>    floor_part = floor_ = math.floor(math.sqrt(n))
>    denom = n - floor_part ** 2
>    result = []
>    result.append(int(floor_))
>
>    if float(denom)!=0:
>       for i in range(boundary-1):
>          try:
>             floor_ = math.floor((math.sqrt(n) + floor_part) / float(denom))
>          except ZeroDivisionError: # perfect square
>             return result
>
>          if denom != 1:
>             result.append(int(floor_))
>          floor_part = denom * floor_ - floor_part
>          coeff = denom
>          denom = n - floor_part ** 2
>          common_div = fractions.gcd(coeff, denom)
>          coeff /= common_div
>          denom /= common_div
>
>          if denom == 1:
>             result.append(int(floor_part + result[0]))
>    return result
>
> def faktorisasi_default(n, kelipatan, boundary, faktor_1, faktor_2, flag):
>     q = cfract(n*kelipatan, boundary)
>     p = [0, q[0]]
>     Q = [1]
>     A = [0, 1, q[0]]
>     Q.append(((n*kelipatan)-(p[1]**2))/Q[0])
>     # i = 2
>     for i in range(2,len(q)):
>         p.append((q[i-1]*Q[i-1])-p[i-1])
>         Q.append(((n*kelipatan)-(p[i]**2))/Q[i-1])
>         A.append((q[i-1]*A[i]+A[i-1])%(n*kelipatan))
>     #tabel sudah selesai
>
>     for i in range(0,len(Q)):
>         for j in range(i+1,len(Q)):
>             if flag and Q[i]==Q[j]:
>                 print Q[i]
>                 print Q[j]
>                 temp = Q[i]
>                 tempA1 = A[i+1]
>                 tempA2 = A[j+1]
>
>                 temp2 = tempA1*tempA2 % n # nilai base
>
>                 if temp2 > Q[i]:
>                     faktor_1 = int(fractions.gcd(temp2+temp, n))
>                     faktor_2 = int(fractions.gcd(temp2-temp, n))
>
>                     if faktor_1 != 1 and faktor_2 != 1:
>                         flag = False
>
>     return faktor_1, faktor_2, flag
>
> def faktorisasi(n):
>     flag = True
>     faktor_1, faktor_2 = 1, 1
>     j=1 #kelipatan
>     boundary=50 #iterasi CFRAC
>     faktor_1, faktor_2, flag = faktorisasi_default(n, j, boundary,
> faktor_1, faktor_2, flag)
>     while (flag):
>        j+=1
>        boundary*=2
>        print "Nilai boundary : %d" %boundary
>        print "Nilai j : %d" %j
>        faktor_1, faktor_2, flag = faktorisasi_default(n, j, boundary,
> faktor_1, faktor_2, flag)
>     return faktor_1, faktor_2
>
> if __name__ == '__main__':
>     import sys
>     if len(sys.argv) > 1:
>         n = int(sys.argv[1])
>     else:
>         n = 94152743499601547 #untuk difaktorkan
>     faktor_1, faktor_2 = faktorisasi(n)
>     print faktor_1
>     print faktor_2
>
>
> --
> Martin A. Brown
> http://linux-ip.net/
>