素数判定法について

摘要

1より大きい整数nが与えられたとき，nが素数であるかどうかを判定するという問題（素数判定問題）が非常に古い問題であることに間違いはない．素因数分解の一意性が初等整数論の出発点であると考えれば，素数をたくさん作り出したいというのは数学者としては自然な欲求であるし，それが大きい数になれば，素数であることを知るのに何らかの工夫をしなければいけなかったであろう．実際，多くの数学者ヤアマチュアがこの問題に携わってきた．1970年代に素因数分解の困難さに基づくRSA暗号が発明され，その鍵生成に大きな素数を高速に作り出すことは工学的な要請になり，それがこの間題に関する研究を数学者の（あるいは趣味の）世界から解放し，大きな発展を促した．