Uint64 で表現できる素数の最大値は 18446744073709551557

TL; DR _{^{（今北産業）}}

1. 符号なしINT64（UINT64）が扱える最大値は 18,446,744,073,709,551,615（2^64-1）

2. 上記より小さく、一番大きい素数は 18,446,744,073,709,551,557

3. 以下は Go 言語（以下 golang）による算出

   main.go

   package main
   
   import (
       "fmt"
       "math"
       "math/big"
   )
   
   func main() {
       // uint64の最大値を取得
       maxUint64 := new(big.Int).SetUint64(math.MaxUint64) // =2^64-1 =18446744073709551615
   
       // uint64の最大値より小さく、最大の素数を見つける
       prime := new(big.Int).Set(maxUint64)
       for !isPrime(prime) {
           prime.Sub(prime, big.NewInt(1)) // prime--
       }
   
       fmt.Println("The largest prime less than", maxUint64, "is:", prime)
       // Output:
       // The largest prime less than 18446744073709551615 is: 18446744073709551557
   }
   
   // isPrime は n が素数の場合 true を返す。
   // n が 2^64 より小さければ、100% 素数判定ができる。
   func isPrime(n *big.Int) bool {
       // 2未満の数値は素数ではない
       if n.Cmp(big.NewInt(2)) < 0 {
           return false
       }
   
       return n.ProbablyPrime(0)
   }
   

• オンラインで動作を見る @ GoPlayground

TS; DR _{^{（あいつら、みんな嘘つき）}}

golang で、素数を使ってゴニョゴニョしていたら、静的解析ツール（golangci-lint）から「uint --> int の型変換でオーバーフローするリスクあり」的なお叱りを受けました。まれによくある gosec の G115 エラーってやつです。

$ golangci-lint run
totp/example_ecdh_test.go:172:16: G115: integer overflow conversion uint -> int (gosec)
			keyLen = int(outLen)
			            ^

このような場合、「変換前の値が最大値以下であるか」を事前にチェックしておくことでエラーを回避できます。

maxInt16 := uint(32767) // 最大値を決めておく
keyLen := int(maxInt16)

// maxInt16 以下なら変換 & 割り当て。本当は超えていたらエラーにした方が良い。
if outLen < maxInt16 {
    keyLen = int(outLen)
}

さて、今回の俺様プログラムで扱う値は uint64 です。

ふと、「uint64 で扱える最大の素数は何だろう？」と思い「uint64で表現できる素数の最大値」でググってみても、ピンとくるものがありませんでした。

そこで、ググってダメならと Google の噂の双子に聞いてみました。

Gemini「符号なし64bit整数で表現できる素数は 18,446,744,073,709,551,615 です。これは符号なし64bitに格納できる最大の整数です。」

なんか、uint64 の最大値である 18,446,744,073,709,551,615 を素数と言ってきました。

そこで今度は ChatGPT に聞いたら、しれっと 18,446,744,073,709,551,611 と言ってきました。

ほんとだもん！ほんとに ChatGPT がいったんだもん！うそじゃないもん！

しかし、18446744073709551611 をググっても素数であるという情報がありません。

確認のため、Dario Alpern 氏のオンライン素数解析ツール で 18446744073709551615 と 18446744073709551611 を確認してみたところ、やはり素数ではないことがわかりました。

• 18,446,744,073,709,551,615 = 3 × 5 × 17 × 257 × 641 × 65,537 × 6,700,417
• 18,446,744,073,709,551,611 = 11 × 59 × 98,818,999 × 287,630,261

うーん。まぁ、たいした計算量じゃないし、一度わかってしまえば定数として利用できるし、と golang で計算してみることにしました。

$ go run .
The largest prime less than 18446744073709551615 is: 18446744073709551557

• オンラインで計算を見る @ GoPlayground

この値（18,446,744,073,709,551,557）を、先ほどのツールで確認すると素数であることに間違いないようです。あらためて ChatGPT に聞いてみました。

ChatGPT の後出しジャンケン

「サツキもお父さんも、ChatGPT がうそつきだなんて思っていないよ。謝ってるし。メイはきっとインターネットの森の主に会ったんだ。」（隣のトホホより）