Re: Seeking efficient sequential-Carmichael-number generator

Am 20.01.2007 03:21 schrieb Waldek Hebisch:
In comp.lang.lisp robert maas, see http://tinyurl.com/uh3t <rem642b@xxxxxxxxx> wrote:
From: "user923005" <dcor...@xxxxxxxxx>
A program for making Carmichael numbers in source code format:
http://aminet.net/package/dev/src/Carmichael
Download: http://aminet.net/dev/src/Carmichael.lha - View contents

Well I downloaded it, got a gz file, ungzipped it, now have:
4 -rw------- 1 rem user 2835 Jan 18 20:09 Carmichael.lha
which starts like this:
<skipped binary junk>

Do not bother unpacking this archive. The programs is just a
naive double loop (will take hours to get up to 100000000), you
can easily write a better one.

I just extracted the contents for you.

Gottfried Helms


-------Carmichael.readme------------------------------------------------------------
Short: Search for Carmichael Numbers
Uploader: walternn@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx (Norman Walter)
Author: walternn@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx (Norman Walter)
Type: dev/src
Version: 2.0
Requires: Scheme Interpreter (e.g. guile)

Scheme program for finding Carmichael Numbers.
Carmichael Numbers are numbers, which cheat the Fermat Test.

Usage:
======

Step 1: cd into the directority where the file Carmichael.SCM
is located.

Step 2: Call Guile with

guile -l Carmichael.SCM

Step 3: Enter

(carmichael-bis <integer-number>)

Place a integer number for <integer-number>.
The program will compute all Carmichael Numbers
up to this Integer.

Example:

(carmichael-bis 1800)

This will produce the output:

561
1105
1729

These are all Carmichael Numbers up to 1800.


A German manual is also included.



World Wide Web:

http://www.norman-interactive.com (my Homepage)

http://www.informatik.uni-stuttgart.de (University Stuttgart, Dept. of Computer Science)

======================================================================================


----------Carmichael.SCM----------------------------------------------------------
; Carmichael.SCM
; Programm zum Auffinden von Carmichael-Zahlen
; Carmichael-Zahlen sind Zahlen, die den Fermat-Test überlisten.
; 2. überarbeitete Version.
; Autor: Norman Walter
; Version 2.0
; Datum : 8.11.2002

(define (gerade? n)
(= (remainder n 2) 0)
)

(define (quadrat x)
(* x x)
)

; Euklidscher Algorithmus zur Ermittlung des ggT

(define (ggT a b)
(if (= b 0)
a
(ggT b (remainder a b))
)
)

; Prozedur zur Berechnug der Potenz einer Zahl modulo m.
; Sie verwendet sukzessive Quadratbildung, so daß die Anzahl der
; Schritte logarithmisch mit dem Exponenten wächst.

(define (potmod basis exp m)
(cond ((= exp 0) 1)
((gerade? exp)
(remainder (quadrat (potmod basis (/ exp 2) m))
m))
(else
(remainder (* basis (potmod basis (- exp 1) m))
m))
)
)

; Fermat-Test
; Gibt der Fermat-Test true zurück, so ist die Zahl n mit Sicherheit
; zusammengesetzt. Ergibt er false, so ist nicht ganz sicher, ob
; n wirklich eine Primzahl ist. Sie könnte z.B. eine
; "Basis-2-Pseudoprimzahl" sein.
; In dieser Version wird nicht nur auf 2 hoch (n-1) mod n = 1
; getestet, sondern auf b hoch (n-1) mod n = 1.

(define (fermat b n)
(not (= (potmod b (- n 1) n) 1))
)

(define (kleinster-teiler n)
(finde-teiler n 2)
)

; n hat einen Teiler kleiner oder gleich Wurzel n, wenn es keine
; Primzahl ist. Der Algorithmus muß also nur Teiler zwischen 1
; und Wurzel n überprüfen.

(define (finde-teiler n pruef-teiler)
(cond ( (> (quadrat pruef-teiler) n) n)
( (teilt? pruef-teiler n) pruef-teiler)
(else (finde-teiler n (+ pruef-teiler 1))
)
)
)

(define (teilt? a b)
(= (remainder b a) 0)
)

; Gibt #t zurück, falls n DEFINITIV eine Primzahl ist, sonst #f

(define (primzahl? n)
(= n (kleinster-teiler n))
)

; Liefert #t, falls n Carmichael-Zahl ist, sonst #f

(define (carmichael? n)
(if (eq? (primzahl? n) #f)
(carmichael-iter 1 n)
#f
)
)

; Liefert alle Carmichaelzahlen bis zu einer Obergrenze

(define (carmichael-bis obergrenze)
(carmichael-bis-iter 1 (+ obergrenze 1))
)

(define (carmichael-bis-iter zaehler obergrenze)
(cond ( (< zaehler obergrenze)
(cond ( (carmichael? zaehler)
(display zaehler)
(newline)
)
)
(carmichael-bis-iter (+ zaehler 1) obergrenze)
)
)
)

; Iteration über a:
; Falls für alle 0 < a < n gilt:
; n ist keine Primzahl und
; ggT(a,n) impliziert a hoch (n-1) kongruent 1 modulo n,
; dann ist n eine Carmichael-Zahl.

(define (carmichael-iter a n)

; Implikation:
(if (or (not (= (ggT a n) 1))
(eq? (fermat a n) #f)
)
(if (< a (- n 1))
(carmichael-iter (+ a 1) n)
#t
)
#f
)
)

===================================================================================
----- History txt -----------------------------------------------------------------
history.txt

31.10.2002 - Erste Version 1.0

8.11.2002 - Version 2.0:

Änderungen im Vergleich zu Version 1.0:

Aus

(define (fermat n)
(not (= (potmod 2 (- n 1) n) 1))
)

wurde

(define (fermat b n)
(not (= (potmod b (- n 1) n) 1))
)

Der zusätzliche Parameter b ermöglicht es nun, den Fermat-Test nicht nur
zur Basis 2, sondern zur Basis b durchzuführen.

Die Prozedur

(define (kongruent? a n)
( =
(potmod a (- n 1) n)
(modulo 1 n)
)
)

flog komplet heraus.
Zum einen ist 1 mod n immer 1, zum anderen können wir den gleichen
Test jetzt auch mit der erweiterten Fermat-Prozedur durchführen:

(define (carmichael-iter a n)

; Implikation:
(if (or (not (= (ggT a n) 1))
(eq? (fermat a n) #f)
)
(if (< a (- n 1))
(carmichael-iter (+ a 1) n)
#t
)
#f
)
)

--------------------------------
.

Relevant Pages

  • Re: primality
    ... Fermat tests alone is discouraged. ... composite passing one round is less than 1/4. ... it does detect Carmichael numbers. ...
    (sci.crypt)
  • Re: primality
    ... probability, and the contrary being proven when the RSA or whatever ... Rabin-Miller is for ensuring corner cases like Carmichael numbers, ... Trying whether RSA works is equivalent to Fermat's test. ... Doing Fermat ...
    (sci.crypt)