日本語 English
| 開講年度/ Academic YearAcademic Year |
20252025 |
| 科目設置学部/ CollegeCollege |
理学部/College of ScienceCollege of Science |
| 科目コード等/ Course CodeCourse Code |
CA179/CA179CA179 |
| テーマ・サブタイトル等/ Theme・SubtitleTheme・Subtitle |
素数判定法 |
| 授業形態/ Class FormatClass Format |
対面（全回対面）/Face to face (all classes are face-to-face)Face to face (all classes are face-to-face) |
| 授業形態（補足事項）/ Class Format (Supplementary Items)Class Format (Supplementary Items) |
|
| 授業形式/ Class StyleCampus |
講義/LectureLecture |
| 校地/ CampusCampus |
池袋/IkebukuroIkebukuro |
| 学期/ SemesterSemester |
春学期/Spring SemesterSpring Semester |
| 曜日時限・教室/ DayPeriod・RoomDayPeriod・Room |
土3/Sat.3 Sat.3 ログインして教室を表示する（Log in to view the classrooms.） |
| 単位/ CreditsCredits |
22 |
| 科目ナンバリング/ Course NumberCourse Number |
MAT3430 |
| 使用言語/ LanguageLanguage |
日本語/JapaneseJapanese |
| 履修登録方法/ Class Registration MethodClass Registration Method |
科目コード登録/Course Code RegistrationCourse Code Registration |
| 配当年次/ Assigned YearAssigned Year |
配当年次は開講学部のR Guideに掲載している科目表で確認してください。配当年次は開講学部のR Guideに掲載している科目表で確認してください。 |
| 先修規定/ Prerequisite RegulationsPrerequisite Regulations |
|
| 他学部履修可否/ Acceptance of Other CollegesAcceptance of Other Colleges |
履修登録システムの『他学部・他研究科履修不許可科目一覧』で確認してください。 |
| 履修中止可否/ Course CancellationCourse Cancellation |
〇（履修中止可/ Eligible for cancellation） |
| オンライン授業60単位制限対象科目/ Online Classes Subject to 60-Credit Upper LimitOnline Classes Subject to 60-Credit Upper Limit |
|
| 学位授与方針との関連/ Relationship with Degree PolicyRelationship with Degree Policy |
各授業科目は、学部・研究科の定める学位授与方針（DP）や教育課程編成の方針（CP）に基づき、カリキュラム上に配置されています。詳細はカリキュラム・マップで確認することができます。 |
| 備考/ NotesNotes |
LC191情報科学特論１、RC191情報科学特論１と合同授業 |
Students cultivate a better understanding of primality tests, which are algorithms for determining whether a given natural number is prime, to learn about the key generation of the RSA cryptosystem.
The RSA cryptosystem is the most widely used public-key cryptosystem. Two distinct 1024-bit prime numbers are used as the secret keys of users of RSA. For the key generation of RSA, natural numbers are randomly chosen, and primality tests are used against them. The Miller–Rabin test and Lucas test are well-known primality tests, for example, they are included in FIPS PUB 186-4, which is a standards documentation published by National Institute of Standards and Technology. In this lecture, those two primality tests are discussed. Students learn the efficiency of them by either implementing them on the free software Risa/Asir and performing numerical experiments or hand calculation based on those algorithms.
| 1 | 素数判定法、素数証明法、試し割法、計算量 |
| 2 | 冪演算の高速化、Fermat test |
| 3 | 数式処理ソフト ASIR の使い方 |
| 4 | Carmichael 数 |
| 5 | Miller-Rabin test |
| 6 | プログラミング演習 |
| 7 | 平方剰余 |
| 8 | Lucas test, Frobenius test |
| 9 | Lucas chain |
| 10 | プログラミング演習 |
| 11 | Lucas 擬素数 |
| 12 | Frobenius 擬素数 |
| 13 | Strong Frobenius test |
| 14 | プログラミング演習 |
板書 /Writing on the Board
スライド（パワーポイント等）の使用 /Slides (PowerPoint, etc.)
上記以外の視聴覚教材の使用 /Audiovisual Materials Other than Those Listed Above
個人発表 /Individual Presentations
グループ発表 /Group Presentations
ディスカッション・ディベート /Discussion/Debate
実技・実習・実験 /Practicum/Experiments/Practical Training
学内の教室外施設の利用 /Use of On-Campus Facilities Outside the Classroom
校外実習・フィールドワーク /Field Work
上記いずれも用いない予定 /None of the above
| 補足事項 (Supplementary Items) |
|---|
| 計算方法の理論を講義室で説明し、プログラミング演習は計算機室で実施します。 |
授業時間外の学習に関する指示は、必要に応じて別途指示する。
| 種類 (Kind) | 割合 (%) | 基準 (Criteria) |
|---|---|---|
| 平常点 (In-class Points) | 100 |
出席態度(49%) 数回の小レポート(51%) |
| 備考 (Notes) | ||
| 特になし | ||
| その他 (Others) | |||||
|---|---|---|---|---|---|
| 特になし。 |
| その他 (Others) | |||||
|---|---|---|---|---|---|
| 特になし |
任意に与えられた自然数が素数であるか否かを判定するアルゴリズム（素数判定法）の理解を深めることで，RSA 暗号における鍵生成について学ぶ．
Students cultivate a better understanding of primality tests, which are algorithms for determining whether a given natural number is prime, to learn about the key generation of the RSA cryptosystem.
RSA 暗号は現在最も広く利用されている公開鍵暗号であり，二つの相異なる 1024 bit 長の素数がユーザーの秘密鍵として使用されている．RSA 暗号の鍵生成では，ランダムに生成された自然数に対して素数判定法を実行される．代表的な素数判定法に Miller-Rabin test と Lucas test があり，例えばアメリカ国立標準技術研究所 (NIST) が発行している標準規格書 FIPS PUB 186-4 でも採用されている．この講義では Miller-Rabin test と Lucas test について説明する．さらにこれらをフリーソフトである数式処理システム Risa/Asir を用いて実装して数値実験を行うか, アルゴリズムにそった手計算によって, これらのアルゴリズムの効率性について学習する．
The RSA cryptosystem is the most widely used public-key cryptosystem. Two distinct 1024-bit prime numbers are used as the secret keys of users of RSA. For the key generation of RSA, natural numbers are randomly chosen, and primality tests are used against them. The Miller–Rabin test and Lucas test are well-known primality tests, for example, they are included in FIPS PUB 186-4, which is a standards documentation published by National Institute of Standards and Technology. In this lecture, those two primality tests are discussed. Students learn the efficiency of them by either implementing them on the free software Risa/Asir and performing numerical experiments or hand calculation based on those algorithms.
| 1 | 素数判定法、素数証明法、試し割法、計算量 |
| 2 | 冪演算の高速化、Fermat test |
| 3 | 数式処理ソフト ASIR の使い方 |
| 4 | Carmichael 数 |
| 5 | Miller-Rabin test |
| 6 | プログラミング演習 |
| 7 | 平方剰余 |
| 8 | Lucas test, Frobenius test |
| 9 | Lucas chain |
| 10 | プログラミング演習 |
| 11 | Lucas 擬素数 |
| 12 | Frobenius 擬素数 |
| 13 | Strong Frobenius test |
| 14 | プログラミング演習 |
板書 /Writing on the Board
スライド（パワーポイント等）の使用 /Slides (PowerPoint, etc.)
上記以外の視聴覚教材の使用 /Audiovisual Materials Other than Those Listed Above
個人発表 /Individual Presentations
グループ発表 /Group Presentations
ディスカッション・ディベート /Discussion/Debate
実技・実習・実験 /Practicum/Experiments/Practical Training
学内の教室外施設の利用 /Use of On-Campus Facilities Outside the Classroom
校外実習・フィールドワーク /Field Work
上記いずれも用いない予定 /None of the above
| 補足事項 (Supplementary Items) |
|---|
| 計算方法の理論を講義室で説明し、プログラミング演習は計算機室で実施します。 |
授業時間外の学習に関する指示は、必要に応じて別途指示する。
| 種類 (Kind) | 割合 (%) | 基準 (Criteria) |
|---|---|---|
| 平常点 (In-class Points) | 100 |
出席態度(49%) 数回の小レポート(51%) |
| 備考 (Notes) | ||
| 特になし | ||
| その他 (Others) | |||||
|---|---|---|---|---|---|
| 特になし。 |
| その他 (Others) | |||||
|---|---|---|---|---|---|
| 特になし |