Adleman-Rumely法について,くわしい内容を教えてください
1980年に発表された完全な素数判定で、100桁ぐらいの整数に対応できるようです。
 図書館で調べても、インターネットで調べても、内容(アルゴリズム)まで載っているものはありませんでした。どなたか詳しく載っている本、紹介しているホームページを教えてください。よろしくお願いします。
 ちなみにAdleman-Rumely法は数学的な(整数論)バックグラウンドがかなり必要だそうです。 

このQ&Aに関連する最新のQ&A

A 回答 (2件)

「コンピュータと素因子分解」和田秀男著


発行遊星社・発売星雲社
ISBN4-7952-6889-4
本体2000円+税

の第7章にずばり解説されてます。
手元にある本によると
1999年4月に改訂版第1刷発行とありますから
まだ手に入ることでしょう。
また、同じ著者による

「高速乗算法と素数判定」
上智大学講究録No.15

という本にも解説されています。
そちらのお求めは、
東大赤門前の有隣社(03-3814-0275)か
東大病院前(というか旧数学科の前)のマテマティカ
(03-3816-3724)まで。
本格的に勉強なされるのでしたら、

「A Course in Computational Algebraic Number Theory」Henri Cohen著
Graduate Texts in Mathematics 138,
Springer-Verlag
ISBN3-540-55640-0
ISBN0-387-55640-0

を手元に置かれると宜しいかと思われます。
書き込むのが遅すぎましたかもしれませんが、
お役に立てれば幸いです。
    • good
    • 0

回答になってないんですが...


APR Testというやつ。話にしか聞いてません。多項式時間に非常に近い高速な方法だそうで、今時のPCなら100桁どころじゃないでしょう。
 という訳で、この際、面白そうだから探してみましたが駄目ですねえ。でも、1990年頃に改良版が出たようで、Googleで探すと→Bosma, W. and van der Hulst, M.-P. ``Faster Primality Testing.'' Advances in Cryptology, Proc. Eurocrypt '89, Springer-Verlag, 652-656, 1990. が出てきました。この文献は、国会図書館http://www.ndl.go.jp/の検索(タイトル=Eurocrypt ,刊行=1990年)でヒットしますから、コピー入手可能でしょう。また、国内の何処やらの大学の修論発表会のリストにも載ってますから、その大学に問い合わせる手もあるかも。
 なお、他にも楕円関数論を使った高速な方法がある。もちろんこの分野の話を理解するには最低限代数学・ゼータ関数の知識は要求されるでしょうから、いっぱい勉強しないといけないですね。
    • good
    • 0

このQ&Aに関連する人気のQ&A

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!

このQ&Aを見た人が検索しているワード

このQ&Aと関連する良く見られている質問

Q素数の覚え方

素数を覚えたいのですが、どんな語呂合わせが良いでしょうか?100以下の物を覚えたいと思ってます。

2 3 5 7 11 13・・・・・

Aベストアンサー

ネット上にいくつかありました。
(11~103)
http://homepage2.nifty.com/takeshin/information/karan_koron.htm
(2~29)
http://www1.kcn.ne.jp/~zubat/seisuuseisitu/seisitu5.htm

ただちょっと分かりづらいような気がしたので、自分で作ってみました。

生き別れた母からの手紙は届かず、父親や兄弟とも死別し、妻も無く会社倒産のあおりで職も失った29歳男性の悲哀を頭に思い浮かべながら覚えてください。

文(ふみ)来ない(2,3,5,7,11)
父さんいない(13,17)
逝く兄さん(19,23)
29歳身無し人(29,31,37,41)
嫁は至難(43,47)
この身は困苦(53,59)
無為なろくでなし(61,67)
無い涙で泣く(71,73,79)
破産波及で(83,89)
苦難の日々(97,101)

素数を思い出すたびに暗~い気持ちになったらすみません。

Q6桁~8桁の整数を2桁で表現する方法について

いつも大変お世話になっております。

何卒よろしくお願い致します。


標題の件になります。

例えば、

1000000(7桁) という数字と 888888(6桁) という数字があります。
このそれぞれの値を、100以内で表現するには(2桁)どのような
公式を用いればよろしいでしょうか。

お手数をお掛けしますが、何卒よろしくお願い致します。

Aベストアンサー

こんにちは。

もっともまともな方法として、N進法で表すことを考えます。
2桁以内で表すのですから、
√1000000 = 1000
つまり、1001進法以上にする必要があり、そのためには、1001種類以上の文字種が必要になります。
それほどの文字種となると、漢字を使うのが適当と思います。
たとえば、JISのコード順に、0,1,2,3・・・1001を漢字に当てはめる、とかです。

イメージとしては、
1000000 → 鯵頭
888888  → 麿軋
みたいな感じで。


あと、
1000000 や 888888 のように単純な規則性がある数字列であるならば、
データ圧縮の考え方が使えるかもしれませんね。
たとえば「0が6個連続」を「鮨」と表すとか、「8だけ6個」を「殉」と表すとかです。


以上、ご参考になりましたら。

QちょっとHな化学記号の覚え方

 質問の場所が ここでいいか わからなかったので ここで 質問します

 化学記号の 覚え方に 横の列は「すいへーりーべ ぼくのふね 」
って 水素 ヘリウムの 順序を 覚えるのは みなさん ご存じだと
思います

 ところが 今日 小耳にはさんだのに タテの列の覚え方は 少し
色っぽい 覚え方が あると 聴きましたが どういう 覚え方かは
知りません

  He Ne Ar Kr Xe Rn この元素の覚え方 で そういうの 知ってる方
おられたら 教えてください

Aベストアンサー

私はこんなのを教えてもらいました。

(縦第1列)
H Li Na K Rb Cs Fr
変な淋病何故かゆい、ラブしすぎてフラフラ
(縦第15列)
N P As Sb Bi
ニッポンの朝は酢豚にビール
(縦第16列)
O S Se Te Po
オスの性器はテッポウだ
(縦第17列)
F Cl Br I At
ふっくらブラジャー私もアタック

ご参考まで

Q整数を実数、非整数を複素数に対応させたら?

タイトルのらと?の間にに屁理屈を加えることになりそうですが、関数をグラフ化する場合、時々表記のような疑問が湧くことがあります。これは又離散と連続をつなぐようなことにも関係があるかなと愚考する次第ですが、如何でしょうか。

Aベストアンサー

こんにちは、まだありました。
#2よりやさしいと思います。
それは、相当性(一意性の条件)についてです。
これは、
1. 任意のa:実数に対して、
aの整数部分と小数部分が一意に決まるという内容です。
2. また、任意のz:複素数に対して、
zの実数部分と虚数部分が一意に決まるということも成り立ちます。

証明は省略させて下さい。暇があれば証明も載せたいと思います。

ご質問の趣旨にあった回答になっているかどうか分かりませんが、とりあえず回答しました。

Q干支の覚え方

月の異名(睦月、如月、弥生・・・)の語呂的な覚え方は教えて!gooであったのですが、干支の覚え方(子、丑、寅・・・)の語呂的な覚え方はありませんでした。
やはり「ね、うし、とら、う、たつ・・・」の王道(?)で覚えなくてはならないのでしょうか。
もし語呂的な覚え方があれば教えてください。お願いします。

Aベストアンサー

同じ悩みを抱えていた方々が、過去にいらっしゃいましたね。(笑)
http://oshiete1.goo.ne.jp/kotaeru.php3?q=2455736
http://oshiete1.goo.ne.jp/kotaeru.php3?q=147875

やはり、前半後半それぞれ6個1組で覚えるのがよいんでしょうね。


もうご存知の情報でしてたら、すみません。

Q2^a=3^bを満たす整数(正の整数、0、負の整数)はa=b=0のみ。これは2と3に限った話なのか。

2^a=3^bを満たす整数(正の整数、0、負の整数)はa=b=0のみですがこれは2と3に限った話なのか。
それとも
A^a=B^bとおくと
4^a=5^b
2^a=4^b
などのようにA,Bは正の整数ならばなんでもいいのか。それともA,Bは互いに素など条件がありますか。

A,Bともに正の整数でかつA,Bは互いに素のときA^a=B^bを満たす整数a,bはa=b=0のみ。
なのか
A,Bともに正の整数のときA^a=B^bを満たす整数a,bはa=b=0のみ。
なのか。どちらですか。

さらにA,Bは負の整数、0ではダメだと思っていますがこれは正しいでしょうか。

Aベストアンサー

A^a=B^b で、AとBが互いに素でなければ、a=b=0以外が存在します。

2^2=4^1
6^2=3^4

81^a=64^b は、a=b=0 のみ

Q炎色反応の覚え方

質問のとおりですが炎色反応のいい覚え方教えてください。前から知りたいと想っていました。それと元素記号の覚え方も教えてください。

Aベストアンサー

 いくつか回答は出ているようですが,過去にも類似質問がありましたのでご紹介しておきます。

「QNo.138 「水兵リーベ僕の船・・・」の続きをおしえて。」
 http://www.okweb.ne.jp/kotaeru.php3?q=138

「QNo.66819 炎色反応」
 http://www.okweb.ne.jp/kotaeru.php3?q=66819

「QNo.66898 元素の周期表」
 http://www.okweb.ne.jp/kotaeru.php3?q=66898

「QNo.83835 水兵リーベ・・・続きは?」
 http://www.okweb.ne.jp/kotaeru.php3?q=83835

「QNo.291920 ちょっとHな化学記号の覚え方」
 http://www.okweb.ne.jp/kotaeru.php3?q=291920


 他にもあるかもしれません。トップページで「炎色反応」や「元素記号」,「化学記号」,「周期表」等で検索してみると良いですよ。

参考URL:http://www.okweb.ne.jp/index.php3

 いくつか回答は出ているようですが,過去にも類似質問がありましたのでご紹介しておきます。

「QNo.138 「水兵リーベ僕の船・・・」の続きをおしえて。」
 http://www.okweb.ne.jp/kotaeru.php3?q=138

「QNo.66819 炎色反応」
 http://www.okweb.ne.jp/kotaeru.php3?q=66819

「QNo.66898 元素の周期表」
 http://www.okweb.ne.jp/kotaeru.php3?q=66898

「QNo.83835 水兵リーベ・・・続きは?」
 http://www.okweb.ne.jp/kotaeru.php3?q=83835

「QNo.291920 ちょっとHな化学記号の覚...続きを読む

Q整数問題(素数)

(p+1)(q+2)(r+3)=4pqr
を満たす素数p,q,rの組を全て求めよ。

絞り込み方がわかりません。
よろしくお願いします。

Aベストアンサー

(p+1)(q+2)(r+3)=4pqr
両辺をpqrで割ると
(1+1/p)(1+2/q)(1+3/r)=4
1+1/p≦3/2,1+2/q≦2であるから
(3/2)*2*(1+3/r)≧4
3+9/r≧4
r≦9
rは2,3,5,7のいずれか

r=2の場合
5(p+1)(q+2)=8pq
p,qのいずれかは5 あとは簡単

r=3の場合
6(p+1)(q+2)=12pr
(p+1)(q+2)=2pr
左辺を展開し整理すると
pr-2p-r-2=0
(p-1)(r-2)=6 あとはかけて6になる組合せを考えればよいだけ。

r=5の場合
2(p+1)(q+2)=5pq
p,qのいずれかは2

r=7の場合
5(p+1)(q+2)=14pq
p,qのいずれかは5

こんな感じですかね

Q周期表のHな覚え方

一般的な覚え方は「水平リーベ僕の船・・・」だと思いますが、Hな覚え方があると聞きました。
知っていたら教えてください。

Aベストアンサー

参考URLを見ましょう \(^o^)/

http://www.d2.dion.ne.jp/~hmurata/goro.html

参考URL:http://www.d2.dion.ne.jp/~hmurata/goro.html

Q3桁の整数の表し方と証明

各位の数字が全て異なり各位とも0でない3桁の整数がある。この整数の各位の数字を入れ替えて出来る全ての整数ともとの整数を加えると222の倍数になることを証明せよ。という問題ですが、、

もとの3桁整数を表すのに100a+10b+cと考えました。
各位を入れ換えた整数を例えば100b+10c+aとすると加えると101a+110b+11cとなります。これが222の倍数となると証明できないし、、。最初の3桁の整数の表し方が違うんですかね、、。すいません、教えて下さい。

Aベストアンサー

専門家じゃないので間違ってるかもです。

三桁の数をabcとすると、
abc=100a+10b+c
となり、入れ替えてできる数は、
100a+10c+b
100b+10a+c
100b+10c+a
100c+10a+b
100c+10b+a
の計六種類となり、これらを足すと
200(a+b+c)+20(a+b+c)+2(a+b+c)
と表すことができます。
これらを(a+b+c)でくくると、
(a+b+c)(200+20+2)
となり、222の倍数となることが証明できると思います。

質問者さんは考え方はあってると思いますが、
問題の読み方で少し勘違いが生じたものとおもいます。


人気Q&Aランキング

おすすめ情報