流れる空の中で数学を。

とある数学好きの「手作りすうがく」と「気ままな雑記」。

【無料キャンペーン】｢たす・ひく・かける・わる｣だけで数学入門【Kindle】

Kindle 数学 twitter

Twitterのフォロワーさんが3414人(円周率)に到達したのを記念して、9月9日～9月13日に下記の本の無料キャンペーンを実施します。ぜひ、この機会に読んでみてください!!

www.amazon.co.jp

これから中学数学を始める人、微分積分初めての人、復習したい人、大学数学をのぞいてみたい人に特におすすめです。

【Python】素因数分解のプログラム

プログラミング オリジナル 数学

Amazon.co.jp: Yoshiki Ueoka:作品一覧、著者略歴

数学関連の絶版本・品切れ本をコチラから購入できます！

自然数nを２つの因数に分解するプログラムを書きました。21桁の例で約200秒前後です。16桁だと、0.3秒程度です。

 

factorization ver1.ipynb

【Python】ボツになった素因数分解アルゴリズム【数論】

オリジナル プチ研究 プログラミング 数学 素因数分解

数学関連の絶版本・品切れ本をコチラから購入できます！

この記事では、自然数nが素数p,qを用いて、

n=pq

と表される場合を考える。このnからp,qを高速に求めたい。そこで、[text:sqrt{n}]と比べて大きすぎず小さ過ぎない適当な自然数m \ge 2をとり、

x= [\sqrt{n} ] - ([\sqrt{n} ] \mod m)

とすると、

x \equiv 0 \mod m

x\sim O(\sqrt{n})

となる。ここで、整数平方根のプログラムを用いた。

 

sky-time-math.hatenablog.jp

 

これを用いて、nを

n=(x-cm+a)(x+dm+b)

と表すことにする。ここで、 0 \lt a,b\lt mは\gcd(a,m)=\gcd(b,m)=1を満たす自然数である。

式変形して、

M:=n^2-x^2=\{(d-c)m+a+b\}x-cdm^2+(ad-bc)m+ab

となる。ここで、a,b \lt mがc,dに比べて十分小さいとすると*1、この式は次のように近似できるはずである。

M\sim \{(d-c)m+a+b\}x-cdm^2

これをdについて解くと、

d\sim \frac{M-(a+b)x+cm}{m(x-cm)}

となる。md \lt xなので、更に変形して、

c \lt \frac{x^2+(a+b)x-M}{m+m x}\sim \frac{x}{m}

となる。cをこの範囲でループさせて、x-cm+aがnを割り切るか調べれば良い。

aの数の候補は、トーシェント関数\phi(m)となるので、このアルゴリズムの計算量は、

\frac{\phi(m)}{m}x\sim\frac{\phi(m)}{m}\sqrt{n}

となる。mを２から始まる素数の連続した積p_1 p_2 \cdots p_rにとることで、この計算量を短縮できる。このときの計算量は

(1-1/2)(1-1/3)\cdots(1-1/p_r)\sqrt{n}

となる。

しかし、これだけ短縮してもrsa100は残念ながら分解できなかった。こんなアイデアではダメなんだろう。もっと革新的なアイデアが必要なはずだ。

*1:これは、２つの素因数p,qが近すぎないことを意味する。このとき、c,d \gt 0である。

【Python】巨大な数の整数平方根

プログラミング 数学

Amazon.co.jp: Yoshiki Ueoka:作品一覧、著者略歴

数学関連の絶版本・品切れ本をコチラから購入できます！

探しても見つからなかったので、巨大な(大きな)自然数nに対して、高速に整数平方根を計算するプログラムを書きました。整数平方根とはnに対して、

m\lt \sqrt{n}

となる最大の整数のことです。math.sqrt等のライブラリ関数を使うと、誤差が出てしまいますが、以下の関数Intsqrtはnの桁数の計算量で整数平方根を厳密に計算してくれます。

Intsqrt

 

【Kindle】｢たす・ひく・かける・わる｣だけで数学入門【入門書】

Kindle 数学

僕の数学の入門書がついに出版されました!!

「たす・ひく・かける・わる」だけで数学入門 数と関数をめぐって: 中学数学入門から大学数学入門までを１冊に | 上岡 良季 | 数学 | Kindleストア | Amazon

f:id:FoxQ:20200815220835j:plain

ついに、(僕が?)待ちに待った1冊が出版されました!!
本当に最小限の予備知識である四則演算だけで、中高大の数学へ入門できる究極の1冊です!!
公式や定理、計算も飛ばさず、これでもかというくらい丁寧に説明しています。
これから数学を始める人も、忘れてしまった人も、昔やったことを思い出したい人も、数式アレルギー治したい人もみんなみんなにオススメの1冊です。

中学数学では、数と関数などについて、

高校数学では、複素数、微分、積分などについて、

大学数学では、マクローリン展開、オイラーの公式、微分方程式、パデ近似などについて、

それぞれ解説しています。この本は既刊｢多点総和法入門｣の入門書にもなっていますし、これから出版予定の本の入門書にもなっています。つまり、全てのはじまりの数学入門書なのです!!

まずは、試し読みしてみてください。内容が気に入ったらぜひ購入して読んでいただきたいです。なんと、破格のワンコイン500円です。ページ数は元の原稿で約130ページです。ここにぎゅっと数学入門の全てが詰まっています。

では、巻末でまたお会いできることを期待しています。