How to resolve the algorithm Carmichael 3 strong pseudoprimes step by step in the BASIC programming language

Published on 12 May 2024 09:40 PM
#Basic

How to resolve the algorithm Carmichael 3 strong pseudoprimes step by step in the BASIC programming language

Table of Contents

Problem Statement

A lot of composite numbers can be separated from primes by Fermat's Little Theorem, but there are some that completely confound it. The   Miller Rabin Test   uses a combination of Fermat's Little Theorem and Chinese Division Theorem to overcome this. The purpose of this task is to investigate such numbers using a method based on   Carmichael numbers,   as suggested in   Notes by G.J.O Jameson March 2010.

Find Carmichael numbers of the form: where   (Prime1 < Prime2 < Prime3)   for all   Prime1   up to   61. (See page 7 of   Notes by G.J.O Jameson March 2010   for solutions.)

For a given

P r i m

e

1

{\displaystyle Prime_{1}}

Chernick's Carmichael numbers

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Carmichael 3 strong pseudoprimes step by step in the BASIC programming language

Source code in the basic programming language

for i = 3 to max_sieve step 2
	isprime[i] = 1
next i

isprime[2] = 1
for i = 3 to sqr(max_sieve) step 2
	if isprime[i] = 1 then
		for j = i * i to max_sieve step i * 2
			isprime[j] = 0
		next j
	end if
next i

subroutine carmichael3(p1)
	if isprime[p1] <> 0 then
		for h3 = 1 to p1 -1
			t1 = (h3 + p1) * (p1 -1)
			t2 = (-p1 * p1) % h3
			if t2 < 0 then t2 = t2 + h3
			for d = 1 to h3 + p1 -1
				if t1 % d = 0 and t2 = (d % h3) then
					p2 = 1 + (t1 \ d)
					if isprime[p2] = 0 then continue for
					p3 = 1 + (p1 * p2 \ h3)
					if isprime[p3] = 0 or ((p2 * p3) % (p1 -1)) <> 1 then continue for
					print p1; " * "; p2; " * "; p3
				end if
			next d
		next h3
	end if
end subroutine

for i = 2 to 61
	call carmichael3(i)
next i
end


100 cls
110 max_sieve = 10000000 ' 10^7
120 dim isprime(max_sieve)
130 sub carmichael3(p1)
140  if isprime(p1) = 0 then goto 440
150 for h3 = 1 to p1-1
160   t1 = (h3+p1)*(p1-1)
170   t2 = (-p1*p1) mod h3
180   if t2 < 0 then t2 = t2+h3
190   for d = 1 to h3+p1-1
200    if t1 mod d = 0 and t2 = (d mod h3) then
210     p2 = 1+int(t1/d)
220     if isprime(p2) = 0 then goto 270
230     p3 = 1+int(p1*p2/h3)
240     if isprime(p3) = 0 or ((p2*p3) mod (p1-1)) <> 1 then goto 270
250     print format$(p1,"###");" * ";format$(p2,"####");" * ";format$(p3,"#####")
260    endif
270   next d
280  next h3
290 end sub
300 'set up sieve
310 for i = 3 to max_sieve step 2
320  isprime(i) = 1
330 next i
340 isprime(2) = 1
350 for i = 3 to sqr(max_sieve) step 2
360  if isprime(i) = 1 then
370   for j = i*i to max_sieve step i*2
380    isprime(j) = 0
390   next j
400  endif
410 next i
420 for i = 2 to 61
430  carmichael3(i)
440 next i
450 end


' version 17-10-2016
' compile with: fbc -s console

' using a sieve for finding primes

#Define max_sieve 10000000 ' 10^7
ReDim Shared As Byte isprime(max_sieve)

' translated the pseudo code to FreeBASIC 
Sub carmichael3(p1 As Integer) 

  If isprime(p1) = 0 Then Exit Sub

  Dim As Integer h3, d, p2, p3, t1, t2

  For h3 = 1 To p1 -1
    t1 = (h3 + p1) * (p1 -1)
    t2 = (-p1 * p1) Mod h3
    If t2 < 0 Then t2 = t2 + h3
    For d = 1 To h3 + p1 -1
      If t1 Mod d = 0 And t2 = (d Mod h3) Then
        p2 = 1 + (t1 \ d)
        If isprime(p2) = 0 Then Continue For
        p3 = 1 + (p1 * p2 \ h3)
        If isprime(p3) = 0 Or ((p2 * p3) Mod (p1 -1)) <> 1 Then Continue For
        Print Using "### * #### * #####"; p1; p2; p3
      End If
    Next d
  Next h3
End Sub

' ------=< MAIN >=------

Dim As UInteger i, j

'set up sieve
For i = 3 To max_sieve Step 2
  isprime(i) = 1
Next i

isprime(2) = 1
For i = 3 To Sqr(max_sieve) Step 2
  If isprime(i) = 1 Then
    For j = i * i To max_sieve Step i * 2
      isprime(j) = 0
    Next j
  End If
Next i

For i = 2 To 61
  carmichael3(i)
Next i

' empty keyboard buffer
While InKey <> "" : Wend
Print : Print "hit any key to end program"
Sleep
End

Public isprime[1000000] As Integer

Public Sub Main() 
  
  Dim max_sieve As Integer = 1000000
  Dim i As Integer, j As Integer
  
  'set up sieve
  For i = 3 To max_sieve Step 2 
    isprime[i] = 1 
  Next 
  
  isprime[2] = 1 
  For i = 3 To Sqr(max_sieve) Step 2 
    If isprime[i] = 1 Then 
      For j = i * i To max_sieve Step i * 2 
        isprime[j] = 0 
      Next 
    End If 
  Next 
  
  For i = 2 To 61 
    If isprime[i] <> 0 Then carmichael3(i)
  Next
  
End

Sub carmichael3(p1 As Integer)  
  
  Dim h3 As Integer, d As Integer
  Dim p2 As Integer, p3 As Integer, t1 As Integer, t2 As Integer
  
  For h3 = 1 To p1 - 1 
    t1 = (h3 + p1) * (p1 - 1) 
    t2 = (-p1 * p1) Mod h3 
    If t2 < 0 Then t2 = t2 + h3 
    For d = 1 To h3 + p1 - 1 
      If t1 Mod d = 0 And t2 = (d Mod h3) Then 
        p2 = 1 + (t1 \ d) 
        If isprime[p2] = 0 Then Continue  
        p3 = 1 + ((p1 * p2) \ h3) 
        If isprime[p3] = 0 Or ((p2 * p3) Mod (p1 - 1)) <> 1 Then Continue 
        Print Format$(p1, "###"); " * "; Format$(p2, "####"); " * "; Format$(p3, "#####")
      End If 
    Next
  Next
  
End Sub


max_sieve = 1e7
dim isprime(max_sieve)

//set up sieve
for i = 3 to max_sieve step 2
  isprime(i) = 1
next i

isprime(2) = 1
for i = 3 to sqrt(max_sieve) step 2
  if isprime(i) = 1 then
    for j = i * i to max_sieve step i * 2
      isprime(j) = 0
    next j
  fi
next i

for i = 2 to 61
  carmichael3(i)
next i
end
 
sub carmichael3(p1) 
  local h3, d, p2, p3, t1, t2

  if isprime(p1) = 0  return
  for h3 = 1 to p1 -1
    t1 = (h3 + p1) * (p1 -1)
    t2 = mod((-p1 * p1), h3)
    if t2 < 0   t2 = t2 + h3
    for d = 1 to h3 + p1 -1
      if mod(t1, d) = 0 and t2 = mod(d, h3) then
        p2 = 1 + int(t1 / d)
        if isprime(p2) = 0  continue
        p3 = 1 + int(p1 * p2 / h3)
        if isprime(p3) = 0 or mod((p2 * p3), (p1 -1)) <> 1  continue
        print p1 using ("###"), " * ", p2 using ("####"), " * ", p3 using ("#####")
      fi
    next d
  next h3
end sub


10 FOR p=2 TO 61
20 LET n=p: GO SUB 1000
30 IF NOT n THEN GO TO 200
40 FOR h=1 TO p-1
50 FOR d=1 TO h-1+p
60 IF NOT (FN m((h+p)*(p-1),d)=0 AND FN w(-p*p,h)=FN m(d,h)) THEN GO TO 180
70 LET q=INT (1+((p-1)*(h+p)/d))
80 LET n=q: GO SUB 1000
90 IF NOT n THEN GO TO 180
100 LET r=INT (1+(p*q/h))
110 LET n=r: GO SUB 1000
120 IF (NOT n) OR ((FN m((q*r),(p-1))<>1)) THEN GO TO 180
130 PRINT p;" ";q;" ";r
180 NEXT d
190 NEXT h
200 NEXT p
210 STOP 
1000 IF n<4 THEN LET n=(n>1): RETURN 
1010 IF (NOT FN m(n,2)) OR (NOT FN m(n,3)) THEN LET n=0: RETURN 
1020 LET i=5
1030 IF NOT ((i*i)<=n) THEN LET n=1: RETURN 
1040 IF (NOT FN m(n,i)) OR NOT FN m(n,(i+2)) THEN LET n=0: RETURN 
1050 LET i=i+6
1060 GO TO 1030
2000 DEF FN m(a,b)=a-(INT (a/b)*b): REM Mod function
2010 DEF FN w(a,b)=FN m(FN m(a,b)+b,b): REM Mod function modified

You may also check:How to resolve the algorithm Top rank per group step by step in the Ursala programming language
You may also check:How to resolve the algorithm Rename a file step by step in the C programming language
You may also check:How to resolve the algorithm User input/Text step by step in the Retro programming language
You may also check:How to resolve the algorithm Möbius function step by step in the Ring programming language
You may also check:How to resolve the algorithm Command-line arguments step by step in the Pure programming language