擬素数

 投稿者：永野護  投稿日：2010年 4月 7日(水)11時58分3秒
  2を底とする擬素数を求めよ、という問題です。

定義：ある合成数nがaを底とするフェルマーテストを通るときnをaを底とする擬素数とよぶ。
フェルマーテスト：a^(n-1)<>1 (mod n) であればnは合成数である。（ただしaとnは互いに素）。


次のようなプログラムを書きましたが結果がうまくでません。どこが間違っているのでしょうか。
ご多忙の折まことに恐縮でございますが
ご教示のほどよろしくお願いいたします。(正解は341, 561, 645 らしいです。）

FOR  n=4  TO     1000     REM  2を底とする擬素数を4から1000までの範囲で求める。
IF    MOD(n,2)=0   THEN   GOTO    100   　REM  nが2で割り切れる、すなわちnとaが互いに素で
!      なければ次のnへ行く。
IF  MOD(2^(n-1)-1,n)<>0    THEN   PRINT  n      REM　フェルマーテスト
100
NEXT  n
END 		 

Re: 擬素数

 投稿者：山中和義  投稿日：2010年 4月 7日(水)13時32分5秒
  > No.1157[元記事へ]

永野護さんへのお返事です。

> 2を底とする擬素数を求めよ、という問題です。
> 次のようなプログラムを書きましたが結果がうまくでません。どこが間違っているのでしょうか。

フェルマーテストが間違っていると思います。
OPTION ARITHMETIC RATIONAL !有理数モード（多桁整数）

LET a=2
FOR n=2 TO 1000
   IF GCD(a,n)=1 THEN !aとnは互いに素
      IF MOD(a^(n-1),n)<>1 THEN !フェルマーテスト
      !合成数
      ELSE
         IF PrimeQ(n)=0 THEN PRINT "擬素数=";
         PRINT n
      END IF
   END IF
NEXT n

END

EXTERNAL FUNCTION PrimeQ(n) !素数判定　1:素数、0:素数でない
OPTION ARITHMETIC RATIONAL !有理数モード（多桁整数）
LET PrimeQ=0
IF n<2 OR n<>INT(n) THEN EXIT FUNCTION !引数を確認する
!２以上の自然数なら
IF MOD(n,2)=0 THEN !偶数なら
   IF n=2 THEN LET PrimeQ=1 !２は素数
ELSE !奇数なら
   LET k=3
   DO WHILE k*k<=n !３～√nの奇数のみで検証する
      IF MOD(n,k)=0 THEN EXIT FUNCTION !ひとつでも割り切れるものがあれば素数でない
      LET k=k+2
   LOOP
   LET PrimeQ=1 !最後まで割り切れなければ、素数である
END IF
END FUNCTION
 

Re: 擬素数

 投稿者：永野護  投稿日：2010年 4月 7日(水)14時43分33秒
  > No.1158[元記事へ]

山中和義様へのお返事です。
ご多忙の折、早速のご回答ありがとうございました。
丁寧なプログラムに感謝いたします。
なお質問文に一部記述のみだれたところがありました事をお詫びします。 		 

Re: 擬素数

 投稿者：SECOND  投稿日：2010年 4月 8日(木)15時16分59秒
  > No.1157[元記事へ]

永野護さんへのお返事です。

!ご参考に。下記を、走らせてみてください。
!※素数判定は、速度に余裕が大きく仮なので、別途ご研究下さい。
!
!※「a が n の倍数でない」「a と n が互いに素」を区別しない説明サイトが目立ちます。
!◆フェルマーの小定理
!
! n が素数なら、n の倍数でない整数 a で、mod( a^(n-1), n)=1 を満たす。
!
! しかし、逆に、上の条件と式を満たす n は素数だけでなく、余計がある。
! その余計を、擬素数とよぶ。（素数でないが、それに準ずる意。）
!--------------------------------------------------------------------

OPTION ARITHMETIC RATIONAL !有理数モード
PRINT " a:  素数でないｎで、mod(a^(n-1),n)=1 のｎ"
PRINT "↓: ---------------------------------------"
FOR a=2 TO 15              ! a=11～15 は、有理数モードでないと1000 桁でもオーバーフロー。
   PRINT USING "##:":a;
   !!FOR n=4 TO 1000         !（偶数奇数の両方）走査するｎは、素数 が対象外なので、最小値４から～1000
   FOR n=5 TO 1000 STEP 2  !（奇数のみ）最小５から・・・ 下表と比較するとき。
      IF 0< MOD(a,n) AND MOD(a^(n-1),n)=1 AND 1< Pri(n) THEN PRINT USING "####":n;  !素数でないｎのみ表示。
   NEXT n
   PRINT
NEXT a

FUNCTION Pri(n)
   FOR i=CEIL(n/2) TO 2 STEP -1
      IF MOD(n,i)=0 THEN EXIT FOR
   NEXT i
   LET Pri=i  !素数は i=1 まで下がる。
END FUNCTION

END  !※上のプログラムで出来た表から、奇数のｎだけを見れば下表に一致します。


!表1. 1000 以下の奇数の擬素数と，それが 1000 以下の奇数の合成数に占める割合
!  底 1000 以下の奇数の擬素数 割合
!   2  341, 561, 645 0.9%
!   3   91, 121, 671, 703, 949 1.5%
!   4   15,  85, 91, 341, 435, 451, 561, 645, 703 2.7%
!   5  217, 561, 781 0.9%
!   6   35, 185, 217, 301, 481 1.5%
!   7   25, 325, 561, 703, 817 1.5%
!   8    9,  21, 45, 63, 65, 105, 117, 133, 153, 231, 273,
!        341, 481, 511, 561, 585, 645, 651, 861, 949 6.0%
!   9   91, 121, 205, 511, 671, 697, 703, 949 2.4%
!  10    9, 33, 91, 99, 259, 451, 481, 561, 657, 703, 909 3.3%
!  11   15, 133, 259, 305, 481, 645, 703, 793 2.4%
!  12   65, 91, 133, 143, 145, 247, 377, 385, 703 2.7%
!  13   21, 85, 105, 231, 357, 427, 561 2.1%
!  14   15, 39, 65, 195, 481, 561, 781, 793, 841, 985 3.0%
!  15  341 0.3% 		 

Re: 擬素数

 投稿者：SECOND  投稿日：2010年 4月11日(日)01時43分30秒
  > No.1162[元記事へ]

!※「a が n の倍数でない」「a と n が互いに素」を区別しない説明サイトが目立ちます。
!と、書いたけれども、勿論異なるわけであるが、◆フェルマーの小定理 の場合、
!
!「n が素数」ならば、「n の倍数でない整数 a 」は、自動的に「a と n が互いに素」に
!なってしまう。
!ところが、「擬素数」を探す場合、「n が素数」の条件を持たないために、
!「a が n の倍数でない」が「a と n が互いに素」を、伴うとは限らない。
! 結果として付随していた「a と n が互いに素」の条件は、
! 「擬素数」を探す場合に、別途に必要とするのか？
!
! どなたか、お答え願えれば、助かります。
!
!---------------------------------------------------------
! n=4~1000、a=2~100 まで「n の倍数でない整数 a 」のみと、
!「a と n が互いに素」まで加えた条件の ２通りを比較したが、
! この範囲での差は見られなかった。

OPTION ARITHMETIC RATIONAL !有理数モード
PRINT "  a:  素数でないｎで、mod(a^(n-1),n)=1 のｎ"
PRINT " ↓: ---------------------------------------"
FOR a=2 TO 100
   LET w$=USING$("###",a)& ":"
   FOR n=4 TO 1000  !走査するｎは、素数 が対象外で、4~1000
   !FOR n=5 TO 1000 STEP 2  !偶数を除くとき。
      IF 0< MOD(a,n) AND MOD(a^(n-1),n)=1 AND 1< Pri(n) THEN LET w$=w$& USING$("####",n)
   NEXT n
   PRINT w$
   !----「a と n が互いに素」を加えた条件（ 上と合わせて２行づつ表示。）
   LET w$="    "
   FOR n=4 TO 1000
   !FOR n=5 TO 1000 STEP 2  !偶数を除くとき。
      IF 0< MOD(a,n) AND GCD(a,n)=1 AND MOD(a^(n-1),n)=1 AND 1< Pri(n) THEN LET w$=w$& USING$("####",n)
   NEXT n
   PRINT w$
NEXT a

FUNCTION Pri(n)
   FOR i=CEIL(n/2) TO 2 STEP -1
      IF MOD(n,i)=0 THEN EXIT FOR
   NEXT i
   LET Pri=i  !素数は i=1 まで下がる。
END FUNCTION

END 		 
 

Re: 擬素数

 投稿者：山中和義  投稿日：2010年 4月11日(日)15時03分40秒
  > No.1172[元記事へ]

SECONDさんへのお返事です。

> 「擬素数」を探す場合に、別途に必要とするのか？

概素数
　a^(n-1)≡1 mod n となるnをaを底とする概素数という。a-PRPと記す。

擬素数
　合成数の概素数を擬素数という。

この定義だと
　「aはnの倍数でない」「aとnは互いに素」
は（表立って）ありません。 		 

Re: 擬素数

 投稿者：SECOND  投稿日：2010年 4月11日(日)16時13分21秒
  > No.1158[元記事へ]

ご返事ありがとうございます。実は、このページが難解だったのですが、

・・・という事は、
IF MOD(a^(n-1),n)=1 AND 1< Pri(n) THEN LET w$=w$& USING$("####",n) !擬素数

これだけで、良いとなりますが、確かに一致します。 		 

Re: 擬素数

 投稿者：山中和義  投稿日：2010年 4月12日(月)08時45分36秒
  > No.1174[元記事へ]

SECONDさんへのお返事です。

> これだけで、良いとなりますが、確かに一致します。

擬素数は
　「倍数でない」かつ「互いに素」を満たしている
ということでしょう。

次のような定義(?)もあります。

!擬素数
!　nを合成数とする。1<a<n かつ GCD(a,n)=1 となるある整数aに対して、
!　a^(n-1) ≡ 1 mod n となるとき、nをaを底とする擬素数という。

!擬素数
!　フェルマーテストを通過する合成数 		 

戻る