Java 素因数分解を高速化するには?

f:id:ts0818:20190727173759j:plain

素因数分解」がなんぼのもんじゃい!

どうもボクです。

素因数分解」を高速化する必要が出て参りまして、ちょいと調べてみました。

ちなみに、量子コンピューターとか使えれば、当然、高速化されると。

slpr.sakura.ne.jp

⇧  上記サイト様が詳しいです。だが、しかし!時代は、まだ量子コンピューターを気軽に使える状態ではないと。

というわけで、アルゴリズム探検隊!

 

素因数分解 とは?

高速化を考える前に、そも、「素因数分解」とは何ぞや?

素因数分解 (そいんすうぶんかい、prime factorization) とは、ある正の整数素数の形で表すことである。ただし、1に対する素因数分解は 1 と定義する

素因数分解には次のような性質がある。

素因数分解 - Wikipedia

⇧ とあり、

インターネットでの認証等で利用されている公開鍵暗号の代表であるRSA暗号の安全性は、巨大な合成数素因数分解を実用的な時間内に実行することが困難であることと深い関わりがあり、RSA 以外の公開鍵暗号でも素因数分解問題に基づく方式が多々あるため、素因数分解アルゴリズムが活発に研究されている。また実際に巨大な合成数素因数分解の計算機実験も行われている。

素因数分解 - Wikipedia

⇧ 結構、Webとかのセキュリティに関わってるらしい...

通常の素因数分解は、有理整数環 Z で考えるが、一般の代数体整数環においては、素因数分解の一意性に対応する性質が成り立つとは限らない。

素因数分解 - Wikipedia

素因数分解とは、

例:

360 を素因数分解する。

360 = 23 × 32 × 51

素因数分解 - Wikipedia

のような 素数 × 素数 × ... っていう風な形に表すことであると。

 

素因数分解アルゴリズム

Wikipediaさんによりますと、

正の整数 N を素因数分解するための最も単純な方法は、2 から順に N までの素数で割っていく方法(試し割り法)である。しかし、N が大きくなると、この方法では困難である。

大きな N に対しては以下のような方法がある。

  • ρ法(ポラード・ロー素因数分解法
  • p − 1 法
  • p + 1 法
  • 連分数法
  • 楕円曲線法 (ECM, Elliptic curve method)
  • 複数多項式2次ふるい法 (MPQS, Multiple polynomial quadratic sieve)
  • 数体ふるい法 (NFS, Number field sieve)
    • 一般数体ふるい法 (GNFS, General number field sieve)
    • 特殊数体ふるい法 (SNFS, Special number field sieve)

素因数分解 - Wikipedia

とあるんだと。

んで、Aizu Online Judge の問題で、

judge.u-aizu.ac.jp

時間切れみたいになってしまったんで、アルゴリズムを考えないとアカンのだと。

 

tutuz.hateblo.jp
sucrose.hatenablog.com

んで、「エラトステネスの篩」ってアルゴリズムがイケてるらしい。

yoshikiito.net

⇧  Java 8 の StreamAPI で実装できるようです。

 

時代は「エラトステネスの篩」と思ったら、

etc9.hatenablog.com

⇧  「アトキンの篩」ってのも存在するんだと...もう、どうしたら良いんだろう...。

 

ただ、今回は、

teratail.com

⇧  上記サイト様の方法でイケました。偶数の素数は「2」しか存在しないため、あとは奇数の素数を考えれば良いんだという衝撃。

package main;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class PrimeFactory {

  public static void main(String[] args) {
    // TODO 自動生成されたメソッド・スタブ
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringBuilder sb = new StringBuilder();
    try {
      String strNum = br.readLine();
      sb.append(strNum + ":");
      int number = Integer.parseInt(strNum);
      
      int devideNum = 2; 
      while (number % devideNum == 0) {
        sb.append(" ");
        sb.append(devideNum);
        number /= 2;
      }
     
      devideNum++;
      while (number != 1) {
        if (number % devideNum == 0) {
          sb.append(" ");
          sb.append(devideNum);
          number /= devideNum;
        } else {
          devideNum +=2;
        }
      }

//      for (int i= devideNum; i <= number; i++) {
//        if (number < devideNum) {
//          break;
//        }
//        devideNum = i;
//        while ((number % devideNum) == 0) {
//          number /= devideNum;
//          sb.append(" ");
//          sb.append(devideNum);
//        }
//      }
      
    } catch (IOException e) {
      // TODO 自動生成された catch ブロック
      e.printStackTrace();
    }
    System.out.println(sb.toString());
  }
}

んで、イケました。

f:id:ts0818:20190727193235p:plain

アルゴリズムとか勉強せねばですかね...

今回はこのへんで。