Subscribed unsubscribe Subscribe Subscribe

2017年から30年後の君へ 【素数の年】

あけましておめでとうございます。

昨年中はたくさんのご愛顧をいただきありがとうございました。 本年は2017年卒としての就職が決まりいままでと違う環境へ見切り発車いたします(パソコンカタカタオタクができれば嬉しい)。 就職先に関してはSNS等からRECONして下さい!!! 本年も、昨年と変わらぬご愛顧のほどよろしくお願い申し上げます。

2017年から30年後の君へ

2017年は素数の年

素数は"1"と自分の数でしか割ることのできない孤独の数字です。そして、今年2017年は2011年以来5年ぶりの素数の年です。しかし、人は孤独な素数が好きだ暗号や乱数の生成とかで使いますね…。原子的な素数の判断といえば「エラトステネスのふるい」です。しかし、大きな数では無限に時間がかかります。大きな数字でも「フェルマーの小定理」を用いれば素数を判断することが出来ます。

 「エラトステネスのふるい」とは

1以外の倍数を順次除き残ったものが素数であるとするものです。

1つずつふるいをかける…。

def is_prime(q): 
  i = 2
  while i <=q:
    if q % i == 0:
      return False
    i += 1
  return True


is_prime(2017)
True

is_prime(2047)
False

 「フェルマーの小定理」とは

ap-1 mod p の答えが1以外ならpは合成数である。ただし、aとpが素の関係(最大公約数が1)であること。 もっと単純化するとaに2を代入してqが素数なら答えが1になるということです。

フェルマーの小定理

def is_prime(q):
  q = abs(q)
  if q == 2: return True
  if q < 2 or q&1 == 0: return False
  return pow(2, q-1, q) == 1

is_prime(2017)
True

is_prime(2047)
True

2047は素数?合成数?

お手軽&高速なフェルマーの小定理です。 しかし、これが、真実とは限りません。重大な欠陥があります。 真実を知るための素因数分解

素因数分解

def prime_is(q):
  i = 2
  table = []
  while i * i <= q:
    while q % i == 0:
      q /= i
      table.append(i)
    i += 1
  if q > 1:
    table.append(q)
  return table

prime_is(2047)
[23, 89]

素因数が求まってしまいました…。 23と89を掛けると2047ですね♥ じつは、たまに素数じゃない数もTrueとして通ってしまいます。 フェルマーの小定理の例外である。合成数を「疑素数」といいます。社会のハミ出しモノの皆様のようですね!!!

さいごに

2017年はこのネタで女子との話題に困ったらこの話をしましょう!!!そして、末永く付き合い30年後の「2047年」君にまた同じ話をしましょう。さようなら!!!

参考

2017_Fermat_little_theorem.py · GitHub

Python で素数を求めるアルゴリズムを書いてみる - 集中力なら売り切れたよ

数論入門 I (数学クラシックス)[丸善出版]