(57)【要約】【課題】合成数の非自明な因数を高速に求める因数抽出方法、因数抽出装置を提案する。【解決手段】外部からの入力値及び各演算部の入出力対応を記憶しておく記憶手段と、装置全体を処理制御する制御手段と、多項式を分割するためのパラメータｎを決定するパラメータｎ決定手段と、分割した多項式の多項式演算を行う多項式演算手段と、Ｊａｃｏｂｉ　Ｓｉｇｎａｔｕｒｅ関数のパラメータｗを決定するパラメータｗ決定手段と、Ｊａｃｏｂｉ　Ｓｉｇｎａｔｕｒｅ関数演算を行うＪ−Ｓ演算手段と、等しい組を探索する探索手段と、因数の候補が真の因数であるかどうか判定する判定手段と、によって構成される。【選択図】　図１
2004037759.tif 000002
【特許請求の範囲】
【請求項１】
合成数Ｎを入力して、１，Ｎ以外の因数を出力することを目的とする因数抽出方法であり、
Ｎは自然数Ｐ，Ｑ，ｒに対してＮ＝Ｐ２ｒ×Ｑという形で表現可能な値であり、ＦをＦ（Ｘ１，Ｘ２，…，Ｘｍ）＝Ｃ１Ｘ１＋Ｃ２Ｘ２＋…＋ＣｍＸｍなるｍ変数多項式として、係数Ｃｉ（ｉ＝１，２，…，ｍ）が与えられ、Ｑ＝Ｆ（ｚ１，ｚ２，…ｚｍ）となるｚｉ（ｉ＝１，２，…，ｍ）が存在し、かつそのようなｚｉの候補が有限個で与えられているときに有効な方法であり、
いま各ｚｉの候補数をｋｉ個、その候補をｚｉ，ｊ（ｊ＝１，２，…ｋｉ）としたとき、Ｑ＝Ｆ（ｚ１，ｊ１，ｚ２，ｊ２，…ｚｍ，ｊｍ）となるｚｉ＝ｚｉ，ｊをＪａｃｏｂｉ　Ｓｉｇｎａｔｕｒｅと呼ばれる、ｗ個のＪａｃｏｂｉ記号からなる関数Ｊ（ｗ，Ｎ，ｘ）：＝（（（ｘ＋１）／Ｎ），（（ｘ＋２）／Ｎ），…，（（ｘ＋ｗ）／Ｎ））を利用することで見つけることを特徴とし、
Ｆ（Ｘ１，Ｘ２，…Ｘｍ）を二つの多項式Ｇ（Ｘ１，Ｘ２，…Ｘｎ）＝Ｃ１Ｘ１＋Ｃ２Ｘ２＋…＋ＣｎＸｎ，Ｈ（Ｘｎ＋１，Ｘｎ＋２，…，Ｘｍ）＝Ｃｎ＋１Ｘｎ＋１＋Ｃｎ＋２Ｘｎ＋２＋…＋ＣｍＸｍに分解して、Ｇ，ＨにおけるＸｉ（ｉ＝１，２，…，ｍ）にｚｉ，ｊ（１≦ｊ≦ｋｉ）を代入することで得られるＧｕ（ｕ＝１，２，…，ｋ１ｋ２…ｋｎ），Ｈｖ（ｖ＝１，２，…ｋｎ＋１ｋｎ＋２…ｋｍ）を全て多項式演算手段により計算して、自然数ｗに対して、全てのＧｕ，ＨｖについてＪｕ＝Ｊ（ｗ，Ｎ，Ｇｕ），Ｊｖ＝Ｊ（ｗ，Ｎ，−Ｈｖ）をＪａｃｏｂｉ　Ｓｉｇｎａｔｕｒｅ演算手段で計算し、Ｊｕ＝Ｊｖとなる組を探索手段により探し、そのようなｕ＝ｕ´，ｖ＝ｖ´に対して、Ｇｕ´，Ｈｖ´を生成するｚｉ，ｊからＦ（ｚ１，ｊ１，ｚ２，ｊ２，…ｚｍ，ｊｍ）を計算すると共に、ＮをＦ（ｚ１，ｊ１，ｚ２，ｊ２，…ｚｍ，ｊｍ）で割ることでＦ（ｚ１，ｊ１，ｚ２，ｊ２，…ｚｍ，ｊｍ）がＮの非自明な因数かどうか判定部にて判定し、それが非自明な因数でなければ新たにＪｕ＝Ｊｖとなる組を探して以下同様の処理を繰り返すことで、Ｎの非自明な因数を求める、
ことを特徴とする因数抽出方法。
【請求項２】
請求項１記載の因数抽出方法において、
ｚｉ，ｊ（ｉ＝１，２，…，ｍ，　ｊ＝１，２，…，ｋｉ）に対して、Ｑ＝Ｆ（ｚ１，ｊ１，ｚ２，ｊ２，…，ｚｍ，ｊｍ）となる組が存在しない場合においても、それぞれが互いに素な自然数Ｌ１，Ｌ２，…，Ｌｍ及びＱより大きい自然数Ｌ＝Ｌ１×Ｌ２×…×Ｌｍに対して、Ｆ´をＦ´（Ｘ１，Ｘ２，…，Ｘｍ，Ｙ）＝Ｃ１Ｘ１＋Ｃ２Ｘ２＋…＋ＣｍＸｍ＋ＬＹなる（ｍ＋１）変数多項式として、係数Ｃｉ（ｉ＝１，２，…，ｍ），Ｌが与えられ、Ｑ＝Ｆ´（ｚ´１，ｚ´２，…，ｚ´ｍ，ｓ）となるｚ´ｉ（ｉ＝１，２，…ｍ），ｓが存在し、かつＦの係数Ｃｉ（ｉ＝１，２，…，ｍ）がそれぞれＬ／Ｌｉを約数に持つような整数であれば有効な方法であり、
その場合に、ｚ１，ｊ，ｚｍ，ｊをそれぞれｚ１，ｊ＋ｙ１，ｊＬ１，ｚｍ，ｊ＋ｙｍ，ｊＬｍと置き換え、得られる全てのＧｕ，Ｈｖに対して−Ｃ１Ｌ１＜Ｇｕ≦０，−ＣｍＬｍ＜Ｈｖ≦０が満たされるよう整数ｙ１，ｊ，ｙｍ，ｊを決定することでｓの候補を０以上（Ｃ１Ｌ１＋ＣｍＬｍ）／Ｌ未満に決定させ、Ｇ´（Ｘ１，Ｘ２，…Ｘｎ，Ｙ）＝Ｃ１Ｘ１＋Ｃ２Ｘ２＋…＋ＣｎＸｎ＋ＬＹとして、Ｇ´におけるＸ１にｚ１，ｊ＋ｙ１，ｊＬ１，Ｙにｓ´（０≦ｓ´＜（Ｃ１Ｌ１＋ＣｍＬｍ）／Ｌ），ＨにおけるＸｍにｚｍ，ｊ＋ｙｍ，ｊＬｍ，Ｇ´，ＨにおけるＸｉ（ｉ＝２，３，…，ｍ−１）にｚｉ，ｊを代入することで得られるＧ´ｔ（ｔ＝１，２，…，ｋ１ｋ２…ｋｎ（Ｃ１Ｌ１＋ＣｍＬｍ）／Ｌ），Ｈｖ（ｖ＝１，２…，ｋｎ＋１ｋｎ＋２…ｋｍ）を全て多項式演算手段により計算して、自然数ｗに対して、全てのＧ´ｔ，ＨｖについてＪｔ＝Ｊ（ｗ，Ｎ，Ｇ´ｔ），Ｊｖ＝Ｊ（ｗ，Ｎ，−Ｈｖ）をＪａｃｏｂｉ　Ｓｉｇｎａｔｕｒｅ演算手段で計算し、Ｊｔ＝Ｊｖとなる組を探索手段により探し、そのようなｔ＝ｔ´，ｖ＝ｖ´に対して、Ｇ´ｔ´，Ｈｖ´を生成するｚｉ，ｊ，ｙ１，ｊ，ｙｍ，ｊ，ｓ´からＦ（ｚ１，ｊ１＋ｙ１，ｊＬ１，ｚ２，ｊ２，…，ｚｍ−１，ｊｍ−１，ｚｍ，ｊｍ＋ｙｍ，ｊＬｍ）＋Ｌｓ´を計算すると共に、ＮをＦ（ｚ１，ｊ１＋ｙ１，ｊＬ１，ｚ２，ｊ２，…，ｚｍ−１，ｊｍ−１，ｚｍ，ｊｍ＋ｙｍ，ｊＬｍ）＋Ｌｓ´で割ることでＦ（ｚ１，ｊ１＋ｙ１，ｊＬ１，ｚ２，ｊ２，…，ｚｍ−１，ｊｍ−１，ｚｍ，ｊｍ＋ｙｍ，ｊＬｍ）＋Ｌｓ´がＮの非自明な因数かどうかを判定手段により判定し、それが非自明な因数でなければ新たにＪｔ＝Ｊｖとなる組を探して以下同様の処理を繰り返すことで、Ｎの非自明な因数を求める、
ことを特徴とする因数抽出方法。
【請求項３】
因数抽出方法に用いられる因数抽出装置であって、
外部からの入力値及び各演算部の入出力対応を記憶しておく記憶手段と、
装置全体を処理制御する制御手段と、
多項式を分割するためのパラメータｎを決定するパラメータｎ決定手段と、
分割した多項式の多項式演算を行う多項式演算手段と、
Ｊａｃｏｂｉ　Ｓｉｇｎａｔｕｒｅ関数のパラメータｗを決定するパラメータｗ決定手段と、
Ｊａｃｏｂｉ　Ｓｉｇｎａｔｕｒｅ関数演算を行うＪａｃｏｂｉ　Ｓｉｇｎａｔｕｒｅ演算手段と、
等しい組を探索する探索手段と、
因数の候補が真の因数であるかどうか判定する判定手段と、
を具備する因数抽出装置。
【請求項４】
コンピュータが読み取り可能な符号によって記述され、上記請求項１または２記載の因数抽出方法を実行する因数抽出プログラム。
【請求項５】
請求項４記載の因数抽出プログラムをコンピュータが読み取り可能な記憶媒体に記憶した因数抽出プログラムを記録した記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は合成数の非自明な因数を高速に求めることを目的とするための因数抽出方法及びその装置、プログラムを記録した記録媒体に関するものであり、主に大きな素因子を持つ合成数の素因数分解の困難性が重要な問題となる情報セキュリティの分野に関する。
【０００２】
【従来の技術】
従来の技術として例えば、千田、内山、斉藤「Ｎ＝ｐｒ×ｑ型の合成数（ｒは大きい）に対する新しい素因数分解アルゴリズム」ＳＣＩＳ２０００、電子情報通信学会情報セキュリティ研究専門委員会主催、２０００年がある。これは合成数Ｎが素数ｐ，ｑ，自然数ｒに対してＮ＝ｐｒ×ｑという形に限定した場合の素因数分解方法を与えており、具体的にはそれぞれが互いに素でＬ＝Ｌ１×Ｌ２×…×Ｌｍ＞ｑを満たすような自然数Ｌｉを用意し、任意のＬｉがＮと互いに素であればｐの値に関わらずｐｒｋｉ＝１（ｍｏｄ　Ｌｉ）となるような最小の自然数ｋｉ（ｋｉはＬｉ−１の約数）が求められることから、Ｎｋｉ＝ｐｒｋｉｑｋｉ＝ｑｋｉ（ｍｏｄＬｉ）についてｑ（ｍｏｄ　Ｌｉ）のｋｉ個の候補を計算できることを利用している。更にいえば、Ｍｉ＝Ｌ／Ｌｉ，Ｎｉ＝１／Ｍｉ（ｍｏｄ　Ｌｉ），Ｎｋｉ＝Ｚｉｋｉ（ｍｏｄ　Ｌｉ）を満たすＺｉの組に対してｑ´＝Ｍ１Ｎ１Ｚ１＋Ｍ２Ｎ２Ｚ２＋…＋ＭｍＮｍＺｍ（ｍｏｄ　Ｌ）とすれば、ｑ＝ｑ´（ｍｏｄ　Ｌ）となるＺｉの組み合わせが必ず存在することが中国人の剰余定理よりいえ、かつそれが計算できることから、ｉ＝１，２，…，ｍについてＮｋｉ＝Ｚｉｋｉ（ｍｏｄ　Ｌｉ）を満たすＺｉの組み合わせを求めることで得られるｑ´が、ｑと等しいかどうかＮを割ってみることで調べる。
【０００３】
【発明が解決しようとする課題】
千田らの従来の方法では、合成数Ｎが素数ｐ，ｑ，自然数ｒに対してＮ＝ｐｒ×ｑという形に限定した場合の素因数分解方法として、Ｎｋｉ＝Ｚｉｋｉ（ｍｏｄ　Ｌｉ）の関係から得られるＺｉの組に対して、ｑ＝Ｍ１Ｎ１Ｚ１＋Ｍ２Ｎ２Ｚ２＋…＋ＭｍＮｍＺｍ（ｍｏｄ　Ｌ）を満たしているかどうか、逐次候補（Ｚ１，Ｚ２，…，Ｚｍ）の組を前記式に代入して実際にＮを割ってみることで判定していた。しかしながらこの方法では単純にｋ１×ｋ２×…×ｋｍ個の候補の組が存在することになり、候補数によっては計算効率が悪い。
【０００４】
本発明では、合成数Ｎに対してＮ＝Ｐ２ｒ×Ｑとなる自然数、Ｐ，ｒ，Ｑが存在すれば、Ｊａｃｏｂｉ　Ｓｉｇｎａｔｕｒｅと呼ばれる、ｗ個のＪａｃｏｂｉ記号からなる関数Ｊ（ｗ，Ｎ，ｘ）＝（（（ｘ＋１）／Ｎ），（（ｘ＋２）／Ｎ），…，（（ｘ＋ｗ）／Ｎ））を利用することで、従来よりも効率良くｑ＝Ｍ１Ｎ１Ｚ１＋Ｍ２Ｎ２Ｚ２＋…＋ＭｍＮｍＺｍ（ｍｏｄ　Ｌ）を満たす（Ｚ１，Ｚ２，…，Ｚｍ）の組を求める方法を与えている。これにより従来よりも効率良い素因数分解方法を実現することができる。
【０００５】
【課題を解決するための手段】
この発明の請求項１では、合成数Ｎを入力して、１，Ｎ以外の因数を出力することを目的とする因数抽出方法であり、
Ｎは自然数Ｐ，Ｑ，ｒに対してＮ＝Ｐ２ｒ×Ｑという形で表現可能な値であり、ＦをＦ（Ｘ１，Ｘ２，…，Ｘｍ）＝Ｃ１Ｘ１＋Ｃ２Ｘ２＋…＋ＣｍＸｍなるｍ変数多項式として、係数Ｃｉ（ｉ＝１，２，…，ｍ）が与えられ、Ｑ＝Ｆ（ｚ１，ｚ２，…ｚｍ）となるｚｉ（ｉ＝１，２，…，ｍ）が存在し、かつそのようなｚｉの候補が有限個で与えられているときに有効な方法であり、
いま各ｚｉの候補数をｋｉ個、その候補をｚｉ，ｊ（ｊ＝１，２，…，ｋｉ）としたとき、Ｑ＝Ｆ（ｚ１，ｊ１，ｚ２，ｊ２，…，ｚｍ，ｊｍ）となるｚｉ＝ｚｉ，ｊをＪａｃｏｂｉＳｉｇｎａｔｕｒｅと呼ばれる、ｗ個のＪａｃｏｂｉ記号からなる関数Ｊ（ｗ，Ｎ，ｘ）＝（（（ｘ＋１）／Ｎ），（（ｘ＋２）／Ｎ），…，（（ｘ＋ｗ）／Ｎ））を利用することで見つけることを特徴とし、
Ｆ（Ｘ１，Ｘ２，…，Ｘｍ）を二つの多項式Ｇ（Ｘ１，Ｘ２，…，Ｘｎ）＝Ｃ１Ｘ１＋Ｃ２Ｘ２＋…＋ＣｎＸｎ，Ｈ（Ｘｎ＋１，Ｘｎ＋２，…，Ｘｍ）＝Ｃｎ＋１Ｘｎ＋１＋Ｃｎ＋２Ｘｎ＋２＋…＋ＣｍＸｍに分解して、Ｇ，ＨにおけるＸｉ（ｉ＝１，２，…，ｍ）にｚｉ，ｊ（１≦ｊ≦ｋｉ）を代入することで得られるＧｕ（ｕ＝１，２，…，ｋ１ｋ２…ｋｎ），Ｈｖ（ｖ＝１，２，…，ｋｎ＋１ｋｎ＋２…ｋｍ）を全て多項式演算手段により計算して、自然数ｗに対して、全てのＧｕ，ＨｖについてＪｕ＝Ｊ（ｗ，Ｎ，Ｇｕ），Ｊｖ＝Ｊ（ｗ，Ｎ，−Ｈｖ）をＪａｃｏｂｉ　Ｓｉｇｎａｔｕｒｅ演算手段により計算し、Ｊｕ＝Ｊｖとなる組を探索手段により探し、そのようなｕ＝ｕ´，ｖ＝ｖ´に対して、Ｇｕ´，Ｈｖ´を生成するｚｉ，ｊからＦ（ｚ１，ｊ１，ｚ２，ｊ２，…，ｚｍ，ｊｍ）＝Ｇｕ´＋Ｈｖ´を計算すると共に、ＮをＧｕ´＋Ｈｖ´で割ることでＧｕ´＋Ｈｖ´がＮの非自明な因数かどうかを判定手段で判定し、それが非自明な因数でなければ新たにＪｕ＝Ｊｖとなる組を探して以下同様の処理を繰り返すことで、Ｎの非自明な因数を求める、因数抽出方法を提案する。
【０００６】
この発明の請求項２では、請求項１記載の因数抽出方法において、
ｚｉ，ｊ（ｉ＝１，２，…，ｍ，　ｊ＝１，２，…，ｋｉ）に対して、Ｑ＝Ｆ（ｚ１，ｊ１，ｚ２，ｊ２，…，ｚｍ，ｊｍ）となる組が存在しない場合においても、それぞれが互に素な自然数Ｌ１，Ｌ２，…，Ｌｍ及びＱより大きい自然数Ｌ＝Ｌ１×Ｌ２×…×Ｌｍに対して、Ｆ´をＦ´（Ｘ１，Ｘ２，…，Ｘｍ，Ｙ）＝Ｃ１Ｘ１＋Ｃ２Ｘ２＋…＋ＣｍＸｍ＋ＬＹなる（ｍ＋１）変数多項式として、係数Ｃｉ（ｉ＝１，２，…，ｍ），Ｌが与えられ、Ｑ＝Ｆ´（ｚ´１，ｚ´２，…，ｚ´ｍ，ｓ）となるｚ´ｉ（ｉ＝１，２，…，ｍ），ｓが存在し、かつＦの係数Ｃｉ（ｉ＝１，２，…，ｍ）がそれぞれＬ／Ｌｉを約数に持つような整数であれば有効な方法であり、
その場合に、ｚ１，ｊ，ｚｍ，ｊをそれぞれｚ１，ｊ＋ｙ１，ｊＬ１，ｚｍ，ｊ＋ｙｍ，ｊＬｍと置き換え、得られる全てのＧｕ，Ｈｖに対して−Ｃ１Ｌ１＜Ｇｕ≦０，−ＣｍＬｍ＜Ｈｖ≦０が満たされるよう整数ｙ１，ｊ，ｙｍ，ｊを決定することでｓの候補を０以上（Ｃ１Ｌ１＋ＣｍＬｍ）／Ｌ未満に決定させ、Ｇ´（Ｘ１，Ｘ２，…，Ｘｎ，Ｙ）＝Ｃ１Ｘ１＋Ｃ２Ｘ２＋…＋ＣｎＸｎ＋ＬＹとして、Ｇ´におけるＸ１にｚ１，ｊ＋ｙ１，ｊＬ１，Ｙにｓ´（０≦ｓ´＜（Ｃ１Ｌ１＋ＣｍＬｍ）／Ｌ），ＨにおけるＸｍにｚｍ，ｊ＋ｙｍ，ｊＬｍ，Ｇ´，ＨにおけるＸｉ（ｉ＝２，３，…，ｍ−１）にｚｉ，ｊを代入することで得られるＧ´ｔ（ｔ＝１，２，…，ｋ１ｋ２…ｋｎ（Ｃ１Ｌ１＋ＣｍＬｍ）／Ｌ），Ｈｖ（ｖ＝１，２…，ｋｎ＋１ｋｎ＋２…ｋｍ）を全て多項式演算手段により計算して、自然数ｗに対して、全てのＧ´ｔ，ＨｖについてＪｔ＝Ｊ（ｗ，Ｎ，Ｇ´ｔ），Ｊｖ＝Ｊ（ｗ，Ｎ，−Ｈｖ）をＪａｃｏｂｉ　Ｓｉｇｎａｔｕｒｅ演算手段により計算し、Ｊｔ＝Ｊｖとなる組を探索手段により探し、そのようなｔ＝ｔ´，ｖ＝ｖ´に対して、Ｇ´ｔ´，Ｈｖ´を生成するｚｉ，ｊ，ｙ１，ｊ，ｙｍ，ｊ，ｓ´からＦ（ｚ１，ｊ１＋ｙ１，ｊＬ１，ｚ２，ｊ２，…，ｚｍ−１，ｊｍ−１，ｚｍ，ｊｍ＋ｙｍ，ｊＬｍ）＋Ｌｓ´＝Ｇ´ｔ´＋Ｈｖ´を計算すると共に、ＮをＧ´ｔ´＋Ｈｖ´で割ることでＧ´ｔ´＋Ｈｖ´がＮの非自明な因数かどうかを判定手段で判定し、それが非自明な因数でなければ新たにＪｔ＝Ｊｖとなる組を探して以下同様の処理を繰り返すことで、Ｎの非自明な因数を求める、因数抽出方法を提案する。
【０００７】
この発明の請求項３では、因数抽出方法に用いられる因数抽出装置であって、外部からの入力値及び各演算部の入出力対応を記憶しておく記憶手段と、装置全体を処理制御する制御手段と、多項式を分割するためのパラメータｎを決定するパラメータｎ決定手段と、分割した多項式の多項式演算を行う多項式演算手段と、Ｊａｃｏｂｉ　Ｓｉｇｎａｔｕｒｅ関数のパラメータｗを決定するパラメータｗ決定手段と、Ｊａｃｏｂｉ　Ｓｉｇｎａｔｕｒｅ関数演算を行うＪａｃｏｂｉＳｉｇｎａｔｕｒｅ演算手段（以下Ｊ−Ｓ演算手段と称す）と、等しい組を探索する探索手段と、因数の候補が真の因数であるかどうか判定する判定手段とを具備する因数抽出装置を提案する。
【０００８】
この発明の請求項４では、コンピュータが読み取り可能な符号によって記述され、請求項１または２記載の因数抽出方法を実行する因数抽出プログラムを提案する。
この発明の請求項５では、請求項４で提案した因数抽出プログラムをコンピュータが読み取り可能な記録媒体に記録した記録媒体を提案する。
【０００９】
【発明の実施の形態】
次に、本発明の実施の形態について図面を参照して詳細に説明する。
第１、第２の実施形態共に、非自明な因数を抽出する対象となる合成数Ｎは、自然数Ｐ、Ｑ、ｒに対してＮ＝Ｐ２ｒ×Ｑという形で表現可能な値であるものとする。
まず第１の実施形態として、請求項１に基づき、ＦをＦ（Ｘ１，Ｘ２，…，Ｘｍ）＝Ｃ１Ｘ１＋Ｃ２Ｘ２＋…＋ＣｍＸｍなるｍ変数多項式として、係数Ｃｉ（ｉ＝１，２，…，ｍ）が与えられ、Ｑ＝Ｆ（ｚ１，ｚ２，…，ｚｍ）となるｚｉ（ｉ＝１，２，…，ｍ）が存在し、かつそのようなｚｉの候補ｚｉ，ｊがそれぞれ有限個ｋｉで与えられているときに有効な因数抽出方法を説明する。
【００１０】
次に第２の実施形態として、請求項２に基づき、従来技術である千田、内山、斉藤によるＮ＝ｐｒ×ｑ型の合成数に対する素因数分解法（ＳＣＩＳ２０００、電子情報通信学会情報セキュリティ研究専門委員会主催、２０００年）を高速化する方法を説明する。
まず第１の実施の形態について説明する。
その際、ＦをＦ（Ｘ１，Ｘ２，…，Ｘｍ）＝Ｃ１Ｘ１＋Ｃ２Ｘ２＋…＋ＣｍＸｍなるｍ変数多項式として、係数Ｃｉ（ｉ＝１，２，…，ｍ）が与えられ、Ｑ＝Ｆ（ｚ１，ｚ２，…，ｚｍ）となるｚｉ（ｉ＝１，２，…，ｍ）が存在し、かつそのようなｚｉの候補ｚｉ，ｊがそれぞれ有限個ｋｉで与えられているものとする。
【００１１】
図１に第１の実施形態における、合成数Ｎ、多項式Ｆの係数Ｃｉ（ｉ＝１，２，…，ｍ），Ｑ＝Ｆ（ｚ１，ｚ２，…，ｚｍ）となるｚｉの候補数ｋｉ及び候補ｚｉ，ｊ（ｉ＝１，２，…，ｊ＝１，２，…，ｋｉ）を入力、Ｎの非自明な因数を出力とする因数抽出装置１１とその内部構成を示す。
入力したＮ，Ｃｉ，ｋｉ，ｚｉ，ｊは記憶手段１３に格納される。また因数抽出装置１１内のデータの入出力操作は制御手段１５によって行われ、各演算手段の入出力関係は制御手段１５より逐次記憶手段１３に格納される。
【００１２】
はじめに、ｋｉ（ｉ＝１，２，…，ｍ）をパラメータｎ決定手段１７に入力する。パラメータｎ決定手段１７は、これを受けて１以上ｍ以下のパラメータｎを出力する。ここではｎの決定方法を一意的には明記しないが、（ｋ１ｋ２…ｋｎ）＋（ｋｎ＋１ｋｎ＋２…ｋｍ）ができるだけ小さくなることが理論的な全体の処理効率化の観点から望ましく、例えば事前にｋｉが与えられているのであれば（ｋ１ｋ２…ｋｎ）＋（ｋｎ＋１ｋｎ＋２…ｋｍ）が最小となるようなｎを探索しても良く、そうでなければある決められた処理時間内で最も（ｋ１ｋ２…ｋｎ）＋（ｋｎ＋１ｋｎ＋２…ｋｍ）が小さい値をとったｎを出力しても良い。しかしＦにおける項の順番は任意に置き換え可能であるため、（ｋ１ｋ２…ｋｎ）＋（ｋｎ＋１ｋｎ＋２…ｋｍ）が最小となるようなｎの探索空間はｍ個の要素に対して組み合わせ的に増大するため、この処理の遅延による影響で必ずしも（ｋ１ｋ２…ｋｎ）＋（ｋｎ＋１ｋｎ＋２…ｋｍ）が最小となるようなｎを選ぶことが全体の処理効率化に繋がるとは限らない。
【００１３】
次にｎが決定したら、Ｃｉ（ｉ＝１，２，…，ｍ），ｚｉ，ｊ（ｉ＝１，２，…，ｍ，ｊ＝１，２，…，ｋｉ），ｎを多項式演算手段１９に入力する。多項式演算手段１９は、これを受けて全てのｚｉ，ｊの組み合わせから得られるＧｕ＝Ｃ１ｚ１，ｊ１＋Ｃ２ｚ２，ｊ２＋…＋Ｃｎｚｎ，ｊｎ（ｕ＝１，２，…，ｋ１ｋ２…ｋｎ），Ｈｖ＝Ｃｎ＋１ｚｎ＋１，ｊｎ＋１＋Ｃｎ＋２ｚｎ＋２，ｊｎ＋２＋…＋Ｃｍｚｍ，ｊｍ（ｖ＝１，２，…，ｋｎ＋１ｋｎ＋２…ｋｍ）を出力する。
一方、Ｊａｃｏｂｉ　Ｓｉｇｎａｔｕｒｅと呼ばれるｗ個のＪａｃｏｂｉ記号からなる関数Ｊ（ｗ，Ｎ，ｘ）＝（（（ｘ＋１）／Ｎ），（（ｘ＋２）／Ｎ），…（（ｘ＋ｗ）／Ｎ））のパラメータｗをパラメータｗ決定手段２１によって決定する。パラメータｗ決定手段２１は、ｋｉを入力とし、ｌｏｇ（ｋ１ｋ２…ｋｍ）以上の最小の整数ｗ＝ｗｍを出力する。これは、Ｇｕ、Ｈｖの計算とは独立であるため、並列に処理することができる。
【００１４】
上記パラメータｗ決定部２１の動作は、因数抽出装置１１が機能するための必要条件ではないが、ｗをｌｏｇ（ｋ１ｋ２…ｋｍ）以上の最小の整数にとることで、因数抽出装置１１の全体の計算量が最も小さくなることが理論的に期待できる。しかし、勿論他の選び方を採ってもよい。
Ｇｕ，Ｈｖ，ｗｍが決定したら、Ｇｕ，Ｈｖ，ｗｍ，ＮをＪ−Ｓ演算手段２３に入力する。Ｊ−Ｓ演算手段２３はＪａｃｏｂｉ　Ｓｉｇｎａｔｕｒｅ関数演算を行う。Ｊ−Ｓ演算手段２３は、これを受けて全てのＧｕ，ＨｖについてＪｕ＝Ｊ（ｗｍ，Ｎ，Ｇｕ），Ｊｖ＝Ｊ（ｗｍ，Ｎ，−Ｈｖ）を出力する。その後、Ｊｕ，Ｊｖ（ｕ＝１，２，…，ｋ　ｋ　…ｋ　，ｖ＝１，２，…，ｋ　ｋ　…ｋ）を探索手段２５に入力し、探索手段２５は、Ｊ，…，ｋ１ｋ２…ｋｎ　，ｖ＝１，２，…，ｋｎ＋１ｋｎ＋２…ｋｍ）を探索手段２５に入力し、探索手段２５は、Ｊｕ´＝Ｊｖ´となるｕ´，ｖ´の組を一つ求めて出力する。そしてその組を判定手段２７に入力し、判定手段２７はｕ´，ｖ´に対応したＧｕ´＝Ｈｖ´及びＮを記憶手段１３から取り出し、Ｇｕ´＋Ｈｖ´＝Ｆ（ｚ１，ｊ１，ｚ２，ｊ２，…，ｚｍ，ｊｍ）が１またはＮの倍数でないか判定し、そうでなければ次にＮを割り切るか判定し、割り切ればそれを因数抽出装置１１の出力結果とし、割り切らないあるいはＧｕ´＋Ｈｖ´が１またはＮの倍数であれば、制御手段１５の制御により探索手段２５が他のｕ´，ｖ´の組を探し、Ｎの因数Ｑ（あるいはＱ以外のＮの非自明な因数）が出力されるまで同様の処理を繰り返す。
【００１５】
この繰り返し処理により必ずＮの非自明な因数が出力される。
上記Ｎの非自明な因数の出力までの処理手順をフローチャートとして図２に示す。
図２において、
ステップＳ１１はパラメータｎ決定手段１７及びパラメータＷ決定手段２１の処理ステップ。
ステップＳ１２は多項式演算手段１９の処理ステップ。
ステップＳ１３はＪ−Ｓ演算手段２３の処理ステップ。
ステップＳ１４は探索手段２５の処理ステップ。
ステップＳ１５〜ステップＳ１７は判定手段２７の内部の処理ステップを示す。
ｑ＝Ｇｕ＋Ｈｖを満たすＧｕ，Ｈｖに対応したＪｕ，ＪｖはＪ−Ｓ演算手段２３より必ず生成される。その理由は、ｑ＝Ｇｕ＋ＨｖであればＪａｃｏｂｉ　Ｓｉｇｎａｔｕｒｅの性質から任意のｗに対して必ずＪｕ＝Ｊｖとなることによる。
【００１６】
逆に、ｗｍを大きく取れば取るほどｑ≠Ｇｕ＋ＨｖかつＪｕ＝Ｊｖとなる確率は小さくなることが理論的に期待でき、特にｗｍをｌｏｇ（ｋ１ｋ２…ｋｍ）以上の最小の整数に取ればｑ≠Ｇｕ＋ＨｖかつＪｕ＝Ｊｖとなるｕ，ｖの組は一つも存在しないことが理論的に期待できる。
次に、第２の実施の形態について説明する。
ここでは先にも述べたように、従来技術である千田、内山、斉藤によるＮ＝ｐｒ×ｑ型の合成数に対する素因数分解法（ＳＣＩＳ２０００、電子情報通信学会情報セキュリティ研究専門委員会主催、２０００年）を高速化する方法を説明する。
【００１７】
千田らの従来の方法は、合成数Ｎが自然数ｐ，ｑ，ｒに対してＮ＝ｐｒ×ｑという形で表現可能な時に適用できるＮの非自明な因数抽出方法であり、Ｎ，ｒ及びｑのサイズｓを入力として、まずそれぞれが互いに素でＬ＝Ｌ１×Ｌ２×…×Ｌｍ＞２ｓを満たすような自然数Ｌｉを用意する。そして任意のＬｉがＮと互いに素であればｐの値に関わらずｐｒｋｉ＝１（ｍｏｄ　Ｌｉ）となるような最小の自然数ｋｉ（ｋｉはＬｉ−１の約数）が求められるから、Ｎｋｉ＝ｐｒｋｉｑｋｉ＝ｑｋｉ（ｍｏｄ　Ｌｉ）の関係を得てｑ（ｍｏｄ　Ｌｉ）のｋｉ個の候補を計算できる。すると、中国人の剰余定理より、Ｍｉ＝Ｌ／Ｌｉ，Ｎｉ＝１／Ｍｉ（ｍｏｄ　Ｌｉ），Ｎｋｉ＝ｚｉｋｉ（ｍｏｄ　Ｌｉ）を満たすＺｉの根ｚｉ，ｊ（ｊ＝１，２，…，ｋｉ）の組に対してｑ´＝Ｍ１Ｎ１ｚ１，ｊ１＋Ｍ２Ｎ２ｚ２，ｊ２＋…＋ＭｍＮｍｚｍ，ｊｍ（ｍｏｄ　Ｌ）とすれば、ｑ＝ｑ´（ｍｏｄ　Ｌ）となる（ｚ１，ｊ１，ｚ２，ｊ２　，…，ｚｍ，ｊｍ）の組み合わせが必ず存在することがいえることから、０≦ｑ´＜Ｌに対しｑ＝ｑ´かどうか逐次Ｎ／ｑ´を計算することで判定していた。
【００１８】
図３に第２の実施形態における、合成数Ｎ、自然数の組（Ｌ１，Ｌ２，…，Ｌｍ）及びＬ＝Ｌ１×Ｌ２×…×Ｌｍ，Ｍｉ＝Ｌ／Ｌｉ，　Ｎｉ＝１／Ｍｉ（ｍｏｄ　Ｌｉ），Ｎｋｉ＝Ｚｉｋｉ（ｍｏｄ　Ｌｉ）を満たすＺｉの根ｚｉ，ｊ（ｉ＝１，２，…，ｍ，ｊ＝１，２，…，ｋｉ）及びその候補数ｋｉを入力、Ｎの非自明な因数を出力とする因数抽出装置５１とその内部構成を示す。
自然数の組（Ｌ１，Ｌ２，…，Ｌｍ）及びその積Ｌ，Ｍｉ＝Ｌ／Ｌｉ，Ｎｉ＝１／Ｍｉ（ｍｏｄ　Ｌｉ），Ｎｋｉ＝Ｚｉｋｉ（ｍｏｄ　Ｌｉ）を満たすＺｉの根ｚｉ，ｊ（ｉ＝１，２，…，ｍ，ｊ＝１，２，…，ｋｉ）及びその候補数ｋｉは、千田らの従来の方法を実現するための演算装置から、Ｎ，ｒ，ｓを入力をとして出力されるものとする。
【００１９】
なお入力ｒについては、実際には計算機のメモリの問題からｒは小さい値とすることができるため、未知であってもｒを推測して、その推測値各々に対して本発明におけるプログラムを実行することも可能である。
入力したＮ、（Ｌ１，Ｌ２，…，Ｌｍ），Ｌ，Ｍｉ＝Ｌ／Ｌｉ，Ｎｉ＝１／Ｍｉ（ｍｏｄ　Ｌｉ），ｋｉ，ｚｉ，ｊは記憶手段５３に格納される。ここでＮｉ，ｚｉ，ｊはＬｉ未満の自然数である。また因数抽出装置５１内のデータの入出力操作は制御手段５５によって行われ、各演算部の入出力関係は制御手段５５より逐次記憶手段５３に格納される。
【００２０】
はじめに、ｋｉ，Ｌｉ，Ｍｉ，Ｎｉ（ｉ＝１，２，…，ｍ），Ｌをパラメータｎ決定手段５７に入力する。パラメータｎ決定手段５７は、これを受けて１以上ｍ以下のパラメータｎを出力する。ここではｎの決定方法を一意的には明記しないが、（ｋ１，ｋ２，…ｋｎ）（Ｍ１Ｎ１Ｌ１＋ＭｍＮｍＬｍ）／Ｌ＋（ｋｎ＋１ｋｎ＋２…ｋｍ）ができるだけ小さくなることが理論的な全体の処理効率化の観点から望ましく、例えば事前にｋｉ，Ｌｉ，Ｍｉ，Ｎｉ，Ｌが与えられているのであれば（ｋ１，ｋ２，…，ｋｎ）（Ｍ１Ｎ１Ｌ１＋ＭｍＮｍＬｍ）／Ｌ＋（ｋｎ＋１ｋｎ＋２…ｋｍ）が最小となるようなｎを探索しても良く、そうでなければある決められた処理時間内で最も（ｋ１，ｋ２，…ｋｎ）（Ｍ１Ｎ１Ｌ１＋ＭｍＮｍＬｍ）／Ｌ＋（ｋｎ＋１ｋｎ＋２…ｋｍ）が小さい値をとったｎを出力しても良い。しかしＦにおける項の順番は任意に置き換え可能であるため、（ｋ１，ｋ２，…ｋｎ）（Ｍ１Ｎ１Ｌ１＋ＭｍＮｍＬｍ）／Ｌ＋（ｋｎ＋１ｋｎ＋２…ｋｍ）が最小となるようなｎの探索空間はｋｉ，Ｌｉ，Ｍｉ，Ｎｉの要素に対して組み合わせ的に増大するため、この処理の遅延による影響で必ずしも（ｋ１，ｋ２，…ｋｎ）（Ｍ１Ｎ１Ｌ１＋ＭｍＮｍＬｍ）／Ｌ＋（ｋｎ＋１ｋｎ＋２…ｋｍ）が最小となるようなｎを選ぶことが全体の処理効率化に繋がるとは限らない。
【００２１】
次にｎが決定したら、Ｍｉ，Ｎｉ（ｉ＝１，２，…，ｍ），ｚｉ，ｊ（ｉ＝１，２，…，ｍ，ｊ＝１，２，…，ｋｉ），Ｌｉ，Ｌｍ，Ｌ，ｎを多項式演算手段５９に入力する。多項式演算手段５９は、これを受けて全てのｚｉ，ｊの組み合わせから得られるＧｕ＝Ｍ１Ｎ１ｚ１，ｊ１＋Ｍ２Ｎ２ｚ２，ｊ２＋…＋ＭｎＮｎｚｎ，ｊｎ＋Ｌｓ（ｕ＝１，２，…，ｋ１ｋ２…ｋｎ，ｓ＝０，１，２，…，（Ｍ１Ｎ１Ｌ１＋ＭｍＮｍＬｍ）／Ｌ−１），Ｈｖ＝Ｍｎ＋１Ｎｎ＋１ｚｎ＋１，ｊｎ＋１＋Ｍｎ＋２Ｎｎ＋２ｚｎ＋２，ｊｎ＋２＋…＋ＭｍＮｍｚｍ，ｊｍ（ｖ＝１，２，…，ｋｎ＋１ｋｎ＋２…ｋｍ）を出力する。
【００２２】
一方、Ｊａｃｏｂｉ　Ｓｉｇｎａｔｕｒｅと呼ばれるｗ個のＪａｃｏｂｉ記号からなる関数Ｊ（ｗ，Ｎ，ｘ）＝（（（ｘ＋１）／Ｎ），（（ｘ＋２）／Ｎ），…，（（ｘ＋ｗ）／Ｎ））のパラメータｗをパラメータｗ決定手段６１によって決定する。パラメータｗ決定手段６１は、ｋｉ，Ｍ１，Ｎ１，Ｌ１，Ｍｍ，Ｎｍ，Ｌｍ，Ｌを入力とし、ｌｏｇ（（ｋ１ｋ２…ｋｍ）（Ｍ１Ｎ１Ｌ１＋ＭｍＮｍＬｍ）／Ｌ）以上の最小の整数ｗ＝ｗｍを出力する。これは、Ｇｕ，Ｈｖの計算とは独立であるため、並列に処理することができる。
【００２３】
上記パラメータｗ決定手段６１の動作は、因数抽出装置５１が機能するための必要条件ではないが、ｗをｌｏｇ（（ｋ１ｋ２…ｋｍ）（Ｍ１Ｎ１Ｌ１＋ＭｍＮｍＬｍ）／Ｌ）以上の最小の整数にとることで、因数抽出装置５１の全体の計算量が最も小さくなることが理論的に期待できる。
Ｇｕ，Ｈｖ，ｗｍが決定したら、Ｇｕ，Ｈｖ，ｗｍ，ＮをＪ−Ｓ演算手段６３に入力する。Ｊ−Ｓ演算手段６３はＪａｃｏｂｉ　Ｓｉｇｎａｔｕｒｅ関数演算を行う。Ｊ−Ｓ演算手段６３は、これを受けて全てのＧｕ，ＨｖについてＪｕ＝Ｊ（ｗｍ，Ｎ，Ｇｕ），Ｊｖ＝Ｊ（ｗｍ，Ｎ，−Ｈｖ）を出力する。その後、Ｊｕ，Ｊｖ（ｕ＝１，２，…，（ｋ１ｋ２…ｋｍ）（Ｍ１Ｎ１Ｌ１＋ＭｍＮｍＬｍ）／Ｌ），ｖ＝１，２，…，ｋｎ＋１ｋｎ＋２…ｋｍ）を探索手段６５に入力し、探索手段６５は、Ｊｕ´＝Ｊｖ´となるｕ´，ｖ´の組を一つ求めて出力する。そしてその組を判定手段６７に入力し、判定手段６７はｕ´，ｖ´に対応したＧｕ´，Ｈｖ´及びＮを記憶手段５３から取り出し、Ｇｕ´，Ｈｖ´が１またはＮの倍数でないか判定し、そうでなければ次にＮを割り切るか判定し、割り切ればそれを因数抽出装置５１の出力結果とし、割り切らないあるいはＧｕ´＋Ｈｖ´が１またはＮの倍数であれば、制御部５５の制御により探索手段６５が他のｕ´，ｖ´の組を探し、Ｎの因数Ｑ（あるいはＱ以外のＮの非自明な因数）が出力されるまで同様の処理を繰り返す。
この繰り返し処理により必ずＮの非自明な因数が出力される。
【００２４】
上記Ｊｕ，Ｊｖ，（ｕ´，ｖ´）の決定及びＮの非自明な因数の出力に関する処理手順をフローチャートとして図４に示す。
図４において、
ステップＳ２１はパラメータｎ決定手段５７の処理ステップ。
ステップＳ２２は多項式演算手段５９の処理ステップ。
ステップＳ２３はパラメータＷ決定手段６１の処理ステップ。
ステップＳ２４はＪ−Ｓ演算手段６３の処理ステップ。
ステップＳ２５は探索手段６５の処理ステップ。
ステップＳ２６〜ステップＳ２８は判定手段６７の処理ステップを示す。
上述した本発明による因数抽出方法はコンピュータが読取可能な符号によって記述された因数抽出プログラムが磁気ディスク或はＣＤ−ＲＯＭのようなコンピュータが読み取り可能な記録媒体に記録され、コンピュータにインストールされてコンピュータ上で因数抽出方法が実行される。或は、通信回線を通じてコンピュータにインストールされて実行される。
【００２５】
【発明の効果】
合成数Ｎが自然数ｐ，ｑ，ｒに対してＮ＝ｐ２ｒ×ｑという形で表現可能な値であり、ｑ＝Ｃ１Ｚ１＋Ｃ２Ｚ２＋…＋ＣｍＺｍとなるＺｉの候補Ｚｉ，ｊ（ｊ＝１，２，…）及び定数Ｃｉが与えられたときにＮの非自明な因数ｑを求める問題に対して、Ｚｉ，ｊを動かしｑ＝Ｃ１Ｚ１，ｊ１＋Ｃ２Ｚ２，ｊ２＋…＋ＣｍＺｍ，ｊｍを満たしているかどうか実際にＮを割ることで判定するよりも効率よくｑ＝Ｃ１Ｚ１，ｊ１＋Ｃ２Ｚ２，ｊ２＋…＋ＣｍＺｍ，ｊｍを満たす（Ｚ１，ｊ１，Ｚ２，ｊ２，…，Ｚｍ，ｊｍ　）の組を求めることができる。
【００２６】
その理由は特に、ｑ＝Ｃ１Ｚ１，ｊ１＋Ｃ２Ｚ２，ｊ２＋…＋ＣｍＺｍ，ｊｍを満たす（Ｚ１，ｊ１，Ｚ２，ｊ２，…，Ｚｍ，ｊｍ）の組を求める問題から、Ｇｕ＝Ｃ１Ｚ１，ｊ１＋ＣｎＺｎ，ｊｎ及びＨｖ＝Ｃｎ＋１Ｚｎ＋１，ｊｎ＋１＋…＋ＣｍＺｍ，ｊｍとしてｑ＝Ｇｕ＋Ｈｖを満たすＧｕ，Ｈｖの組を求める問題に置き換え、そのような組の候補をＪａｃｏｂｉ　Ｓｉｇｎａｔｕｒｅと呼ばれるｗ個のＪａｃｏｂｉ記号からなる関数を利用して絞り込むことで、ｑ＝Ｇｕ＋Ｈｖを満たしているか実際にＮを割ることで判定する処理回数を減らしていることによる。
【図面の簡単な説明】
【図１】この発明の請求項１で提案する因数抽出方法を実現する因数抽出装置の実施例を説明するためのブロック図。
【図２】この発明の請求項１で提案する因数抽出方法の各処理ステップを説明するためのフローチャート。
【図３】この発明の請求項２で提案する因数抽出方法を実現する因数抽出装置の実施例を説明するためのブロック図。
【図４】この発明の請求項２で提案する因数抽出方法の処理ステップを説明するためのフローチャート。
【符号の説明】
１３、５３　　記憶手段　　　　　　　　２３、６３　　Ｊ−Ｓ演算手段
１７、５７　　パラメータｎ決定手段　　２５、６５　　探索手段
１９、５９　　多項式演算手段　　　　　２７、６７　　判定手段
２１、６１　　パラメータｗ決定手段
【図１】
2004037759.tif 000003
【図２】
2004037759.tif 000004
【図３】
2004037759.tif 000005
【図４】
2004037759.tif 000006