２つの素数ｐ，ｑを掛け算した数ｎ＝ｐｑは、ｎが大きな数になるとｎを素因数分解してｐ，ｑを求めるのが容易ではない。そこで、素数のもつこの性質がＲＡＳ暗号に利用されている。
しかし、ｎ未満でｎと互いに素な数ａを選び、ａをｘ乗したａ＾ｘ（ｘ＝０，１，２，．．．）をつくり、各数をｎで割って余りを並べてみると、不思議な周期性が現れる。
例えば、ｎ＝１５の場合には、ｎ＝ｐｑ＝３×５とすぐに計算できるが、この周期性が出現することを確かめてみる。
ａ＝１１を選び、１１＾０，１１＾１，１１＾２，１１＾３を計算すると、１，１１，１２１，１３３１となるので、各々を１５で割って余りを求めると、１，１１， １，１１が得られ、１または１１が周期的に繰り返されることが分かる。
そうすると、
１１＾２＝１５×８＋１
であるから、１１＾２－１を因数分解すると、
１１＾２－１＝（１１－１）×（１１＋１）＝１５×８
と書ける。
ここで得られた１０と１２について、１５と１０、または、１５と１２の最大公約数を求めると、５または３が得られるから、これらがｐ，ｑに相当することが分かる。
ａ＝４を選び、同様の計算をしても、やはり４＾ｘをｎで割った余りには周期２の周期性がみられ、同様にｐ，ｑとして３または５が得られる。ａ＝７の場合には、周期４の周期性が現れる。
一般に、ｎ－１を２乗すると、（ｎ－１）＾２＝ｎ＾２－２ｎ＋１であるから、この数をｎで割ると、余りが１となることがすぐ分かる。そうすると、（ｎ－１）＾ｘ（ｘ＝０，１，２，．．．）をｎで割って余りを求めると、１，ｎ－１，１，ｎ－１，．．．の周期性が現れる。ｎ＋１をｘ乗した数についても同様である。
しかし、ａ＝ｎ－１やｎ＋１の場合には、ｐやｑが現れない。そこで、これらの数を除き、周期性をもつなるべく小さいａを探す計算が必要となるが、ｎが大きな数になると、計算は容易ではない。
ａ＾ｘをｎで割った余りが１になることを、
ａ＾ｘ（ｍｏｄ ｎ）＝１
と表現する（ｘ＝０，１，２，．．．）。これは、ｎを法とするａ＾ｘの剰余が１である、と言い換えてもよい。
ａ＾ｘ（ｍｏｄ ｎ）が周期性をもつとする。ａ＾２（ｍｏｄ ｎ）＝１ならば、ａ＾２ｍ（ｍｏｄ ｎ）＝１である（ｍ＝０，１，２，．．．）。何故なら、ａ＾２＝ｋｎ＋１（ｋ＝１，２，．．．）と書けるから、
ａ＾２ｍ＝（ｋｎ＋１）＾ｍ＝（ｋ＾ｍ）（ｎ＾ｍ）＋．．．＋ｍｋｎ＋１
と展開できる。従って、ａ＾２ｍ（ｍｏｄ ｎ）＝１となる。
さらに、ａ（ｍｏｄ ｎ）＝ａならば、ａ＾（２ｍ＋１）（ｍｏｄ ｎ）＝ａである。何故なら、
ａ＾（２ｍ＋１）（ｍｏｄ ｎ）＝ａ＾２ｍ（ｍｏｄ ｎ）ａ（ｍｏｄ ｎ）
と展開できる。ａ＾２ｍ（ｍｏｄ ｎ）＝１であるから、ａ＾（２ｍ＋１）（ｍｏｄ ｎ）＝ａとなる。
関数ａ＾ｘ（ｍｏｄ ｎ）が周期性をもつならば、この関数をフーリエ級数に展開できる。
ａ＾ｘ（ｍｏｄ ｎ）が周期２の関数ならば、１，ａ，１，ａ，．．．の繰り返しとなる。ａは１でさえなければ任意であるから、簡単のために－１と置き換える。そうすると、ａ＾ｘ（ｍｏｄ ｎ）は関数ｃｏｓｘと表すことができる。ここで、
ｘ＝２ｍのとき：ｘ＝２ｍｐと置き換えると、ｃｏｓｘ＝１
ｘ＝２ｍ＋１のとき：ｘ＝（２ｍ＋１）ｐと置いて、ｃｏｓｘ＝－１
である。円周率パイをｐで表している。
ａ＾ｘ（ｍｏｄ ｎ）が周期４の関数ならば、１，ａ，ｂ，ｃ，１，ａ，．．．の繰り返しとなる。ａ，ｂ，ｃは１でさえなければ任意であるから、それぞれ０，－１，０と置き換える。そうすると、ａ＾ｘ（ｍｏｄ ｎ）は関数ｃｏｓ（ｘ／２）と表すことができる。ここで、
ｘ＝４ｍのとき：ｘ＝４ｍｐと置いて、ｃｏｓ（ｘ／２）＝１
ｘ＝４ｍ＋１のとき：ｘ＝（４ｍ＋１）ｐと置いて、ｃｏｓ（ｘ／２）＝０
ｘ＝４ｍ＋２のとき：ｘ＝（４ｍ＋２）ｐと置いて、ｃｏｓ（ｘ／２）＝－１
ｘ＝４ｍ＋３のとき：ｘ＝（４ｍ＋３）ｐと置いて、ｃｏｓ（ｘ／２）＝０
関数ｆ（ｘ）が、周期２のｃｏｓ関数の項、周期４のｃｏｓ関数の項など、いろいろの周期のｃｏｓ関数の項の足し合わせで構成されているとする。例えば、ｆ（ｘ）の中から周期２の関数ｃｏｓｘだけを抽出するには、フーリエ級数の公式を使えばよい。すなわち、ｆ（ｘ）ｃｏｓｘを積分すれば、ｃｏｓｘに掛けられる係数（振幅に相当する）が求められる。周期２の関数が１つだけなら、結果は１となる。
ｆ（ｘ）とｃｏｓｘの積の積分（内積とも言う）をとると、ｆ（ｘ）中のｃｏｓｘの項だけが残り、ｃｏｓ（ｘ／２），ｃｏｓ（ｘ／４）など他の項とｃｏｓｘとの積の項は０になる。ｃｏｓｘ，ｃｏｓ（ｘ／２）など各周期をもつ関数は互いに直交しているので、その内積をとると、ｃｏｓｘと平行なそれ自身だけが残ることになる。
参考文献
竹内薫著「量子コンピュータが本当にすごい」（ＰＨＰ新書）
しかし、ｎ未満でｎと互いに素な数ａを選び、ａをｘ乗したａ＾ｘ（ｘ＝０，１，２，．．．）をつくり、各数をｎで割って余りを並べてみると、不思議な周期性が現れる。
例えば、ｎ＝１５の場合には、ｎ＝ｐｑ＝３×５とすぐに計算できるが、この周期性が出現することを確かめてみる。
ａ＝１１を選び、１１＾０，１１＾１，１１＾２，１１＾３を計算すると、１，１１，１２１，１３３１となるので、各々を１５で割って余りを求めると、１，１１， １，１１が得られ、１または１１が周期的に繰り返されることが分かる。
そうすると、
１１＾２＝１５×８＋１
であるから、１１＾２－１を因数分解すると、
１１＾２－１＝（１１－１）×（１１＋１）＝１５×８
と書ける。
ここで得られた１０と１２について、１５と１０、または、１５と１２の最大公約数を求めると、５または３が得られるから、これらがｐ，ｑに相当することが分かる。
ａ＝４を選び、同様の計算をしても、やはり４＾ｘをｎで割った余りには周期２の周期性がみられ、同様にｐ，ｑとして３または５が得られる。ａ＝７の場合には、周期４の周期性が現れる。
一般に、ｎ－１を２乗すると、（ｎ－１）＾２＝ｎ＾２－２ｎ＋１であるから、この数をｎで割ると、余りが１となることがすぐ分かる。そうすると、（ｎ－１）＾ｘ（ｘ＝０，１，２，．．．）をｎで割って余りを求めると、１，ｎ－１，１，ｎ－１，．．．の周期性が現れる。ｎ＋１をｘ乗した数についても同様である。
しかし、ａ＝ｎ－１やｎ＋１の場合には、ｐやｑが現れない。そこで、これらの数を除き、周期性をもつなるべく小さいａを探す計算が必要となるが、ｎが大きな数になると、計算は容易ではない。
ａ＾ｘをｎで割った余りが１になることを、
ａ＾ｘ（ｍｏｄ ｎ）＝１
と表現する（ｘ＝０，１，２，．．．）。これは、ｎを法とするａ＾ｘの剰余が１である、と言い換えてもよい。
ａ＾ｘ（ｍｏｄ ｎ）が周期性をもつとする。ａ＾２（ｍｏｄ ｎ）＝１ならば、ａ＾２ｍ（ｍｏｄ ｎ）＝１である（ｍ＝０，１，２，．．．）。何故なら、ａ＾２＝ｋｎ＋１（ｋ＝１，２，．．．）と書けるから、
ａ＾２ｍ＝（ｋｎ＋１）＾ｍ＝（ｋ＾ｍ）（ｎ＾ｍ）＋．．．＋ｍｋｎ＋１
と展開できる。従って、ａ＾２ｍ（ｍｏｄ ｎ）＝１となる。
さらに、ａ（ｍｏｄ ｎ）＝ａならば、ａ＾（２ｍ＋１）（ｍｏｄ ｎ）＝ａである。何故なら、
ａ＾（２ｍ＋１）（ｍｏｄ ｎ）＝ａ＾２ｍ（ｍｏｄ ｎ）ａ（ｍｏｄ ｎ）
と展開できる。ａ＾２ｍ（ｍｏｄ ｎ）＝１であるから、ａ＾（２ｍ＋１）（ｍｏｄ ｎ）＝ａとなる。
関数ａ＾ｘ（ｍｏｄ ｎ）が周期性をもつならば、この関数をフーリエ級数に展開できる。
ａ＾ｘ（ｍｏｄ ｎ）が周期２の関数ならば、１，ａ，１，ａ，．．．の繰り返しとなる。ａは１でさえなければ任意であるから、簡単のために－１と置き換える。そうすると、ａ＾ｘ（ｍｏｄ ｎ）は関数ｃｏｓｘと表すことができる。ここで、
ｘ＝２ｍのとき：ｘ＝２ｍｐと置き換えると、ｃｏｓｘ＝１
ｘ＝２ｍ＋１のとき：ｘ＝（２ｍ＋１）ｐと置いて、ｃｏｓｘ＝－１
である。円周率パイをｐで表している。
ａ＾ｘ（ｍｏｄ ｎ）が周期４の関数ならば、１，ａ，ｂ，ｃ，１，ａ，．．．の繰り返しとなる。ａ，ｂ，ｃは１でさえなければ任意であるから、それぞれ０，－１，０と置き換える。そうすると、ａ＾ｘ（ｍｏｄ ｎ）は関数ｃｏｓ（ｘ／２）と表すことができる。ここで、
ｘ＝４ｍのとき：ｘ＝４ｍｐと置いて、ｃｏｓ（ｘ／２）＝１
ｘ＝４ｍ＋１のとき：ｘ＝（４ｍ＋１）ｐと置いて、ｃｏｓ（ｘ／２）＝０
ｘ＝４ｍ＋２のとき：ｘ＝（４ｍ＋２）ｐと置いて、ｃｏｓ（ｘ／２）＝－１
ｘ＝４ｍ＋３のとき：ｘ＝（４ｍ＋３）ｐと置いて、ｃｏｓ（ｘ／２）＝０
関数ｆ（ｘ）が、周期２のｃｏｓ関数の項、周期４のｃｏｓ関数の項など、いろいろの周期のｃｏｓ関数の項の足し合わせで構成されているとする。例えば、ｆ（ｘ）の中から周期２の関数ｃｏｓｘだけを抽出するには、フーリエ級数の公式を使えばよい。すなわち、ｆ（ｘ）ｃｏｓｘを積分すれば、ｃｏｓｘに掛けられる係数（振幅に相当する）が求められる。周期２の関数が１つだけなら、結果は１となる。
ｆ（ｘ）とｃｏｓｘの積の積分（内積とも言う）をとると、ｆ（ｘ）中のｃｏｓｘの項だけが残り、ｃｏｓ（ｘ／２），ｃｏｓ（ｘ／４）など他の項とｃｏｓｘとの積の項は０になる。ｃｏｓｘ，ｃｏｓ（ｘ／２）など各周期をもつ関数は互いに直交しているので、その内積をとると、ｃｏｓｘと平行なそれ自身だけが残ることになる。
参考文献
竹内薫著「量子コンピュータが本当にすごい」（ＰＨＰ新書）