Prime Factorization в Android

Question

Я разрабатываю небольшое приложение Prime Number для устройств Android, и я почти готов, однако мне бы хотелось помочь с оптимизацией моего класса факторизации.

У меня все еще есть одна или две проблемы с некоторыми большими числами (Even Numbers), которые учитываются в разумные сроки. Я не смогу использовать сито Eratosthenes для этого конкретного проекта, я думаю, так как я могу только просеивать до 10 миллионов, не отключая приложение на моем физическом устройстве (Samsung Galaxy S4 Mini). Итак, моя работа над алгоритмом ниже. Я не уверен, могу ли я сделать алгоритм Поллард Ро, который я реализовал лучше.

Как только я установил, что проверяемое число не является простым или не является простым квадратом, я быстро делаю пробное деление до 10 000, после чего, если число все еще не учитывается полностью, я использую Поллард Rho, чтобы уменьшить его до конца.

Я хочу иметь возможность кодирования чисел в диапазоне 2> 2^64.

Это пример ряда с примерно 15 секунд 256332652145852

Это факторизация [2, 2, 1671053, 38348971].

Любая помощь будет с радостью оценена.

try { 
     long num = Long.valueOf(input); 
     if(num == 1) { 
      return "1" + " = " + input; 
     } else if(num < 1) { 
      return "Cannot factor a number less than 1"; 
     } else if(PrimeNumbers.isPrime(num) == true) { 
      return result = num + " is a Prime Number."; 
     } else if(isSquare(num) == true && PrimeNumbers.isPrime((long) Math.sqrt(num)) == true) { 

      return result = (int) Math.sqrt(num) + "<sup><small>" + 2 + "</small></sup>" + " = " + input; 

     } else { 
      factors(num, pFactors); 
      return result = exponentialForm(pFactors, num) + " = " + input; 
     } 
    } catch(NumberFormatException e) { 
     return result = "Unfortunately the number entered is too large"; 
    } 
} 

public static void factors(long n, ArrayList<Long> arr) { 

    long number = trialDiv(n, arr); 
    if(number > 1) { 
     while(true) { 
      long divisor = pollard(number, 1); 
      if(PrimeNumbers.isPrime(divisor) == true) { 
       number /= divisor; 
       arr.add(divisor); 
       if(PrimeNumbers.isPrime(number) == true) { 
        arr.add(number); 
        break; 
       } 
      } 
     } 
    } 
} 

private static long trialDiv(long n, ArrayList<Long> arr) { 

    while(n % 2 == 0) { 
     n /= 2; 
     arr.add((long) 2); 
    } 

    for(long i = 3; i < 10000; i += 2) { 
     if(PrimeNumbers.isPrime(i) == true) { 
      while(n % i == 0) { 
       arr.add(i); 
       n /= i; 
      } 
     } 
    } 
    if(PrimeNumbers.isPrime(n) == true) { 
     arr.add(n); 
     return 1; 
    } 
    return n; 
} 

public static long pollard(long n, long c) { 

    long x = 2; 
    long y = 2; 
    long d = 1; 

    while (d == 1) { 
     x = g(x, n, c); 
     y = g(g(y, n, c), n, c); 
     d = gcd(Math.abs(y - x), n); 
    } 

    if (d == n) { 
     return pollard(n, c + 1); 
    } else { 
     return d; 
    } 
} 

static long g(long x, long n, long c) { 
    long g = (((x * x) + c) % n); 
    return g; 
} 

static long gcd(long a, long b) { 
    if (b == 0) { 
     return a; 
    } else { 
     return gcd(b, a % b); 
    } 
} 

Answer 1

Ваша функция защиты от загрязнений в порядке, но не велика. Вы используете оригинальный алгоритм Полларда, но лучше использовать вариант Брента. Но это, вероятно, не является источником вашей медленной работы.

Функция пробного деления работает медленно. Проверка каждого возможного делителя на простоту очень дорога и не нужна. Не имеет значения, разделите ли вы на композит; разделение всегда будет терпеть неудачу, но вы не тратите время на проверку примитивности. Лучшим подходом является факторизация колес.