ゴルフの擬似プリズム!

はじめに/背景


最近のディスカッション
暗号チャット私は、フェルマーの素数検定とカーマイケル数。このテストは、 a ^(p-1)mod p
== 1
が素数 p
に対して常に成立することを前提としていますが、カーマイケル番号は本質的にフェルマーのテストの最悪の敵です:
ap とコプライミングしないように選んで a
^(p-1)mod p!= 1
を取得します。現在、 a がコプライムでない場合、基本的に
p
の重要な要素は見当たりません。特に、すべての要因が十分に大きい場合。なぜ、フェルマーテストが実際に何度も実際に使われていない理由(より良いアルゴリズムがあります)は、あなたが防御側として(セキュリティ面で)あなたと同じような仕事をしなければならない数があるからです攻撃者(つまり、数値を計算する)。

なぜなら、これらの数字はいくらか魅力的な理由を知ったところで、可能な限り短時間で生成することになるので、必要なコードがあればそれを覚えることができます。

Carmichael numbers are also known as A002997 on
OEIS
.
There is a related
challenge
already, but entries from there are not competitive
here because they are optimized for speed as opposed to size. The
same argument holds for the inverse direction, entries here are
likely to make trade-offs against speed in favor of size.

仕様

入力

This is a standard challenge, so you take a positive or
non-negative integer n as 入力. n may be 0-
or 1-indexed as you prefer (please indicate).

出力

Your 出力 will either be the n-th carmichael number
or the first n carmichael numbers, as you prefer
(please indicate).

仕様

x がコンポジットで、すべての整数 y
gcd(x、y)の場合に限り、 x = 1 であれば、 y ^(x-1)mod x ==
1
を保持します。

誰が勝ちますか?

This is ,
so the shortest code in byte wins!
Standard IO and loophole rules apply.

テストケース

最初のいくつかのcarmichael番号は次のとおりです。

 561,1105,1729,2465,2821,6601,8911,10585,15841,
 29341,41041,46657,52633,62745,63973,75361,101101,
 115921,126217,162401,172081,188461,252601,278545,
 294409,314821,334153,340561,399001,410041,449065,
 488881,512461
ベストアンサー

Mathematica、71バイト

(t=s=1;While[t<=#,If[[email protected]==1&&[email protected],t++]];s)&  

Try it
online!

50->1461241 Try it
online!

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です