- PR -

DoJaでベキ乗剰余演算

1
投稿者投稿内容
ice
会議室デビュー日: 2006/09/24
投稿数: 14
投稿日時: 2006-09-28 12:20
携帯電話上で、1024bitのベキ乗剰余演算を行いたいのですが、DoJaでは、JavaのBigIntegetクラスは使うことはできませんよね？

ベキ乗剰余演算というのは、

c = m^e mod n (ただし，nは素数p,qの積)

（mをe乗したものをnで割ったときの余りをcとする．）

この場合はRSA暗号です。

そして，1024bitといったのは、ｎの部分なのです。

どなたか、1024bitのベキ乗剰余演算を携帯電話上で行う方法を知りませんでしょうか？

よろしくお願い致します。
スフレ
ぬし
会議室デビュー日: 2005/05/27
投稿数: 281
お住まい・勤務地: 東京
投稿日時: 2006-09-28 13:26
引用:

どなたか、1024bitのベキ乗剰余演算を携帯電話上で行う方法を知りませんでしょうか？


BigIntegerと同様な多倍長計算を自分で書けばいいと思います。nativeメソッドを使わないといけない処理でもありませんし。
ice
会議室デビュー日: 2006/09/24
投稿数: 14
投稿日時: 2006-09-28 13:29
引用:


BigIntegerと同様な多倍長計算を自分で書けばいいと思います。nativeメソッドを使わないといけない処理でもありませんし。



やはり自分で書くしかないのですね・・・

どこかに参考になるようなサイトや、ソースコードが載っているサイトはないもんですかね〜
かずくん
ぬし
会議室デビュー日: 2003/01/08
投稿数: 759
お住まい・勤務地: 太陽系第三惑星
投稿日時: 2006-11-01 12:40
奥村晴彦氏らによって書かれた「Javaによるアルゴリズム事典」に多倍長演算がのってたはず。購入して読んでみれば。
http://www.gihyo.co.jp/books/syoseki-contents.php/4-7741-1729-3

ちなみにソースコードだけなら、以下のサイトからダウンロードできます。
http://oku.edu.mie-u.ac.jp/~okumura/java-algo/

追加：
回答先が
http://www.atmarkit.co.jp/bbs/phpBB/viewtopic.php?topic=34564&forum=13&3
の間違い。すまん。

[ メッセージ編集済み 編集者: かずくん 編集日時 2006-11-02 12:11 ]
ぷさいくろう
ぬし
会議室デビュー日: 2006/08/30
投稿数: 1034
投稿日時: 2006-11-01 13:05
c = m^e mod n (ただし，nは素数p,qの積)
だったら数学使ったら？
明智重蔵
大ベテラン
会議室デビュー日: 2005/09/05
投稿数: 127
投稿日時: 2006-11-02 09:32
引用:

ぷさいくろうさんの書き込み (2006-11-01 13:05) より:
c = m^e mod n (ただし，nは素数p,qの積)
だったら数学使ったら？



なるほど
中学生の数学ですね

(226*620) mod 7

226=32*7+2
620=88*7+4

因数分解して
226*620=(32*7+2)*620

((32*7+2)*620) mod 7
= (2*620) mod 7
= (2*(88*7+4)) mod 7
= (2*4) mod 7

すなわち

(226*620) mod 7
= ((226 mod 7) * (620 mod 7) ) mod 7

ようするに
複数の数の積をnで割った余りは
複数の数をnで割った余りの積を、nで割った余り

あとは簡単

declare
c pls_Integer;
m pls_Integer;
e pls_Integer;
n pls_Integer;
begin
m := 5;
e := 20;
n := 13*17;
c := 1;

for i in 1..e Loop
c := mod(c*m,n);
end Loop;

DBMS_Output.Put_Line(c);
DBMS_Output.Put_Line(mod(power(5,20),13*17));
end;
/


[ メッセージ編集済み 編集者: 明智重蔵 編集日時 2006-11-02 10:25 ]
1

スキルアップ／キャリアアップ（JOB@IT）