# 伪素数和Fermat素性检验

## **判断素数**

$$n$$为素数$$\Longleftrightarrow$$对任意$$b,\left(b,n\right)=1$$，$$b^{n-1}\equiv 1\left(\mod n\right)$$或$${\mathrm{ord}}\_{n}{\left(b\right)}\mid n-1$$

## $$n$$**对基**$$b$$**的伪素数**

$$n$$为奇合数，$$\left(b,n\right)=1$$，$$b^{n-1}\equiv 1\left(\mod n\right)$$

* 存在无穷个对基$$2$$的伪素数
* 若$$n$$为对基$$b\_1,b\_2$$的伪素数，则$$n$$为对基$$b\_1\cdot b\_2$$的伪素数
* 若$$n$$为对基$$b$$的伪素数，则$$n$$为对基$$b^{-1}$$的伪素数
* 若存在$$b$$使得$$b^{n-1}\not\equiv 1\left(\mod n\right)$$，则模$$n$$的简化剩余系中至少有一半的的数满足$$b^{n-1}\not\equiv 1\left(\mod n\right)$$

## **Fermat素性检验**

> * **STEP1:** 随机选取整数$$b$$和安全参数$$t$$
> * **STEP2:** 计算$$r\equiv b^{n-1}\left(\mod n\right)$$
> * **STEP3:** 若$$r\not=1$$，则$$n$$为合数
> * **STEP4:** 重复$$t$$次

## **Carmichael数**

合数$$n$$满足对任意$$b,\left(b,n\right)=1$$，$$b^{n-1}\equiv 1\left(\mod n\right)$$

存在无穷多个Carmichael数

## **证明**$$n$$**为Carmichael数**

> * **STEP1:** $$n=p\_1\cdots p\_s$$
> * **STEP2:** $$b^{p\_i-1}\equiv 1\left(\mod p\_i\right)$$
> * **STEP3:** $$b^{n-1}\equiv 1\left(\mod p\_i\right)$$


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://chenyangwang.gitbook.io/mathematical-base-for-information-safety/su-xing-jian-yan/wei-su-shu-he-fermat-su-xing-jian-yan.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.