Phương pháp để xác minh số Carmichael

Trong lý thuyết số, số Carmichael là một hợp số n thỏa mãn quan hệ đồng dư số học mô-đun: cho tất cả các số nguyên b nguyên tố cùng nhau với n trong khoảng từ 1 đến n. Trong toán học, các số nguyên b và n được gọi là nguyên tố cùng nhau nếu chúng có uớc số chung lớn nhất là 1.

Ý tưởng rất đơn giản, ta lặp qua tất cả các số từ 1 đến n và với mọi số nguyên tố cùng nhau với n, ta kiểm tra xem lũy thừa thứ n-1 của nó theo modulo n có bằng 1 hay không. Ví dụ 1:

• Input: n = 8
• Output: False
• Giải thích: 8 không phải là số Carmichael vì 3 là số nguyên tố cùng nhau với 8 và 3^7 % 8 = 2187 % 8 != 1

Ví dụ 2:

• Input: n = 561
• Output: true

Cài đặt giải thuật

C

#include<stdio.h>
#include<math.h>
const long max=65001;
bool a[max];

void primes()
{
    int i,j,k = (int)sqrt(max);
    for (i = 2; i <= max; i++)
        a[i] = true;
    for (i = 2; i <= k; i++)
        if (a[i])
            for (j = i*i; j <= 65000; j+=i)
                a[j] = false;
}

long mod(long x,long n,long p)
{
    if (n == 1)
        return x % p;
    long ans = mod(x, n/2, p);
    ans = (ans*ans)%p;
    if (n%2 == 1)
        return ans * x % p;
    return ans;
}

int main()
{
    long n;
    primes();
    while (scanf("%ld",&n) != EOF) {
        if (n == 0)
            break;
        int i,flag = 1;
        if (!a[n])
            for (i = 2; i < n; i++)
                if (mod(i, n, n) != i) {
                    flag = 0;
                    break;
                }
        if (flag && !a[n])
            printf("The number %ld is a Carmichael number.\n",n);
        else
            printf("%ld is normal.\n",n);
    }
    return 0;
}

C++

#include <iostream>
using namespace std;
int gcd(int a, int b)
{
    if (a < b)
        return gcd(b, a);
    if (a % b == 0)
        return b;
    return gcd(b, a % b);
}
int power(int x, int y, int mod)
{
    if (y == 0)
        return 1;
    int temp = power(x, y / 2, mod) % mod;
    temp = (temp * temp) % mod;
    if (y % 2 == 1)
        temp = (temp * x) % mod;
    return temp;
}
bool isCarmichaelNumber(int n)
{
    for (int b = 2; b < n; b++) {
        if (gcd(b, n) == 1)
            if (power(b, n - 1, n) != 1)
                return false;
    }
    return true;
}

int main()
{
    cout << isCarmichaelNumber(500) << endl;
    cout << isCarmichaelNumber(561) << endl;
    cout << isCarmichaelNumber(1105) << endl;
    return 0;
}

Java

import java.math.BigInteger;
import java.util.*;

public class Carmichael {
	
	public static boolean isCarmicheal (BigInteger n) {
		
		if (n.isProbablePrime(10)) return false;
		if (n.compareTo(BigInteger.ZERO) == 0 || n.compareTo(BigInteger.ONE) == 0) return false;
		
		boolean flag = true;
		for (BigInteger i = BigInteger.valueOf(2); ((i.compareTo(n)) == -1  && flag == true); i = i.add(BigInteger.ONE)) 
			if (i.gcd(n).compareTo(BigInteger.ONE) == 0) flag &= (i.modPow(n.subtract(BigInteger.ONE), n)).compareTo(BigInteger.ONE) == 0;
		return flag;
	}
	
	public static void main(String[] args){
		Scanner input = new  Scanner(System.in);
		System.out.print("Please Enter a number for n: ");
		
		BigInteger n = input.nextBigInteger();
		int count = 0;
		for(BigInteger i = BigInteger.valueOf(0); i.compareTo(n) == -1; i = i.add(BigInteger.ONE)){
			if(isCarmicheal(i) == true){
				System.out.println(i + " is a Carmicheal number");
				count++;
			}
		}	
		System.out.println("There are a total of " + count + " Carmichael ranging numbers from 1 to " + n);
		input.close();
	}
}

C#

using System;
 
class Carmichael {
    static int gcd(int a, int b)
    {
        if (a < b)
            return gcd(b, a);
        if (a % b == 0)
            return b;
        return gcd(b, a % b);
    }
    static int power(int x, int y, int mod)
    {
        if (y == 0)
            return 1;
 
        int temp = power(x, y / 2, mod) % mod;
        temp = (temp * temp) % mod;
 
        if (y % 2 == 1)
            temp = (temp * x) % mod;
        return temp;
    }
    static int isCarmichaelNumber(int n)
    {
        for (int b = 2; b < n; b++) {
            if (gcd(b, n) == 1)
                if (power(b, n - 1, n) != 1)
                    return 0;
        }
        return 1;
    }
    public static void Main()
    {
        Console.WriteLine(isCarmichaelNumber(500));
        Console.WriteLine(isCarmichaelNumber(561));
        Console.WriteLine(isCarmichaelNumber(1105));
    }
}

Python 3

def gcd( a, b) :
    if (a < b) :
        return gcd(b, a)
    if (a % b == 0) :
        return b
    return gcd(b, a % b)
def power(x, y, mod) :
    if (y == 0) :
        return 1
    temp = power(x, y // 2, mod) % mod
    temp = (temp * temp) % mod
    if (y % 2 == 1) :
        temp = (temp * x) % mod
    return temp
def isCarmichaelNumber( n) :
    b = 2
    while b<n :
        if (gcd(b, n) == 1) :
            if (power(b, n - 1, n) != 1):
                return 0
        b = b + 1
    return 1
print (isCarmichaelNumber(500))
print (isCarmichaelNumber(561))
print (isCarmichaelNumber(1105))

PHP

<?php
function gcd($a, $b)
{
    if ($a < $b)
        return gcd($b, $a);
    if ($a % $b == 0)
        return $b;
    return gcd($b, $a % $b);
}

function power($x, $y, $mod)
{
    if ($y == 0)
        return 1;
    $temp = power($x, $y / 2, $mod) % $mod;
    $temp = ($temp * $temp) % $mod;
    if ($y % 2 == 1)
        $temp = ($temp * $x) % $mod;
    return $temp;
}
 
function isCarmichaelNumber($n)
{
    for ($b = 2; $b <= $n; $b++)
    {
        if (gcd($b, $n) == 1)
            if (power($b, $n - 1, $n) != 1)
                return 0;
    }
    return 1;
}
echo isCarmichaelNumber(500), " \n";
echo isCarmichaelNumber(561), "\n";
echo isCarmichaelNumber(1105), "\n";
?>

Javascript

<script>
    function gcd(a, b)
    {
        if (a < b)
            return gcd(b, a);
        if (a % b == 0)
            return b;
        return gcd(b, a % b);
    }
    function power(x, y, mod)
    {
        if (y == 0)
            return 1;
   
        let temp = power(x, parseInt(y / 2, 10), mod) % mod;
        temp = (temp * temp) % mod;
   
        if (y % 2 == 1)
            temp = (temp * x) % mod;
   
        return temp;
    }
    function isCarmichaelNumber(n)
    {
        for (let b = 2; b < n; b++) {
            if (gcd(b, n) == 1)
                if (power(b, n - 1, n) != 1)
                    return 0;
        }
        return 1;
    }
     
    document.write(isCarmichaelNumber(500) + "</br>");
    document.write(isCarmichaelNumber(561) + "</br>");
    document.write(isCarmichaelNumber(1105));

</script>

view raw Phương pháp để xác minh số Carmichael.md hosted with ❤ by GitHub