dc(1)를 사용하여 소수 생성

dc의 사용법

$ echo "11 32529d1-r|p" | dc
22108

마음대로 수를 세어 보아라

$ od -An -N64 -tx8 /dev/urandom
 6cbff7a8b328a334 cd02607bfca7f24a
 87222740f2b9496d 6e3ace39a3cb82df
 7a6342f2bb52161b 0f468f29f9f3ef56
 b31f49269323dc29 b9d63f2ae7ddb6df

알려진 소수 준비

$ od -An -N64 -tx8 /dev/urandom | \
> sed -ze 's/\(.*\)/\U\1/g; s/[[:space:]]//g'
2F841CA1352FACBCEE4481E502AE1E8286EC562496741EE9B56ECB0085D092733B65E2F685E120F97603CA247A556E39350F64CC55D1B4420EE09FC1CDDB6CA3

일단 써볼게요.

$ for i in `seq 0 9`; do
> curl https://www.kusaremkn.com/prime/$i.txt >>prime.txt;
> done

실행하다

#!/bin/sh

# フェルマの小定理
# fermat(a, n)
fermat() {
	if [ $# -ne 2 ]; then
		return 1
	fi
	if [ `echo "[1sr]sP0sr16i$1 $2d1-r|1=Plrp" | dc` -eq 0 ]; then
		return 1
	fi
	return 0
}

# 素数 (っぽい) かどうか調べる
# isPrime(n)
isPrime() {
	if [ $# -ne 1 ]; then 
		return 1
	fi
	cat prime.txt | while read line; do
		printf "."
		if ! fermat $line $1; then
			printf "#"
			return 1
		fi
	done
}

# 適当な数を思いつく
# randGen()
randGen() {
	od -An -N64 -tx8 /dev/urandom | \
		sed -ze 's/\(.*\)/\U\1/g; s/[[:space:]]//g'
}

RandNum=`randGen`
while ! isPrime $RandNum; do
	RandNum=`randGen`
done
echo
echo "`echo "16i${RandNum}p" | dc` may be prime number."

$ time sh prime.sh

총결산

보충(03-21)

--- prime.sh	2021-03-21 01:46:19.726158589 +0900
+++ prime2.sh	2021-03-21 01:55:52.887732224 +0900
@@ -18,7 +18,7 @@
 	if [ $# -ne 1 ]; then 
 		return 1
 	fi
-	cat prime.txt | while read line; do
+	for line in 2 3 5 7 11 13 17 19; do
 		printf "."
 		if ! fermat $line $1; then
 			printf "#"