Assign-12-10185102232-魏明达.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 华东师范大学计算机科学技术系作业\n",
    "\n",
    "|. |华东师范大学计算机科学技术系作业|. |\n",
    "| :- | :-  | :- |\n",
    "| 课程名称：编程导论Python | 年级：2018级 | 作业成绩： |\n",
    "| 指导教师：兰曼 | 姓名：魏明达 | 姓名：魏明达 |\n",
    "| 专业：计算机系 | 学号：10185102232  |  作业编号： 12  |"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "一、编程实现随机产生1个20位的数，使得该数与111这个数互质。（20分）"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "77654322009142356872\n"
     ]
    }
   ],
   "source": [
    "from random import randint\n",
    "flag = 1\n",
    "while flag:\n",
    "    a = randint(10000000000000000000,99999999999999999999)\n",
    "    if a%3 and a%37:flag = 0\n",
    "print(a)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "二、写Python程序算出$a^xmod b$的值。函数`mod(a, x, b)`返回$a^xmod b$的值。假设$a$和$b$都是最多为10位的整数，而$x$可以是最多为200位的整数。请用递归编写此程序。（20分）"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def mod(a,x,b):\n",
    "    if x == 1: return a%b\n",
    "    if x == 0: return 1%b\n",
    "    p = x//2\n",
    "    q = x-p\n",
    "    s = mod(a,p,b)*mod(a,q,b)\n",
    "    return s%b\n",
    "\n",
    "mod(2,4,7)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "三、世界上常用的一种安全编码方式为RSA，其中产生公钥和私钥的过程中会用到本章介绍的倒数的概念。其实现方式为：给定两个质数$p$，$q$，随机产生一个奇数$e$，满足$e < (p-1)(q-1)$，而且$e$与$(p-1)(q-1)$互质，即$gcd(e, (p-1)(q-1)) = 1$。在$e$的基础上产生$e$的倒数$d$，即$e·d = 1(mod(p-1)(q-1))$。以上过程中产生的$e$即为公钥，$d$即为私钥。\n",
    "<br/>\n",
    "请编程实现求解私钥：对于给定的两个质数$p = 128543041447753$和$q = 1062573853363145487845851$，先随机产生$e < (p-1)(q-1$并且满足$gcd(e, (p-1)(q-1)) = 1$，然后求$d$并打印出来。（20分）"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "13462595594185861890321962687726998157\n"
     ]
    }
   ],
   "source": [
    "from random import randint\n",
    "\n",
    "def extend_gcd(x,y,Vx,Vy):\n",
    "    r = x%y;z = x//y\n",
    "    if r==0:return (y,Vy)\n",
    "    Vx[0] = Vx[0] - z*Vy[0]\n",
    "    Vx[1] = Vx[1] - z*Vy[1]\n",
    "    return extend_gcd(y,r,Vy,Vx)\n",
    "\n",
    "def mod_reverse(e,n):\n",
    "    Vx = [1,0]; Vy=[0,1]\n",
    "    if e>n:\n",
    "        G,X = extend_gcd(e,n,Vx,Vy)\n",
    "        d = X[0]%n\n",
    "    else:\n",
    "        G,X = extend_gcd(n,e,Vx,Vy)\n",
    "        d = X[1]%n\n",
    "    return d\n",
    "\n",
    "\n",
    "p = 128543041447753\n",
    "q = 1062573853363145487845851\n",
    "t = (p-1)*(q-1)\n",
    "flag = 1\n",
    "while flag:\n",
    "    e = randint(1,t)\n",
    "    if e%2 and e%(p-1) and e%(q-1): flag = 0\n",
    "d = mod_reverse(e,t)\n",
    "print(d)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "四、请将<程序：combination_3>的代码改成可以处理L有重复元素的情况。（20分）"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[2, 3],\n",
       " [3, 3],\n",
       " [2, 2],\n",
       " [3, 2],\n",
       " [2, 5],\n",
       " [3, 5],\n",
       " [2, 4],\n",
       " [3, 4],\n",
       " [5, 4],\n",
       " [4, 4],\n",
       " [5, 5],\n",
       " [4, 5]]"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def combination_3(L,k):\n",
    "    if len(L)<=k: return [L]\n",
    "    if k == 0: return [[]]\n",
    "    T1 = combination_3(L[:len(L)-1],k-1)\n",
    "    T2 = combination_3(L[:len(L)-1],k)\n",
    "    T = []\n",
    "    for e in T1:\n",
    "        e.append(L[len(L)-1])\n",
    "        T.append(e)\n",
    "    return T2+T\n",
    "\n",
    "def combination(L,k):\n",
    "    p = combination_3(L,k)\n",
    "    t = []\n",
    "    for i in p:\n",
    "        if not i in t:t.append(i)\n",
    "    return t\n",
    "\n",
    "combination([2,3,3,2,5,4,4,4,5,4,5,4],2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "五、改写<程序：combination_4>。使得从`L`的第一个元素开始考虑，而不是从最后一个开始考虑。也就是说首先考虑一定选择第一个数`L[0]`，然后从剩下的$n-1$个数中选$k-1$个数的组合了然后，一定不选`L[0]`，一定选第二个数`L[1]`，再从剩下的$n-2$个数中选取$k-1$个数的组合；以此类推。（20分）"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[1, 2, 3], [1, 3, 8], [2, 3, 8], [3, 8, 8]]"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def combination_4(L,k):\n",
    "    if k == 0 or len(L)<k:return[[]]\n",
    "    if len(L) == k: return [L]\n",
    "    n = len(L); T = [L[0]];R = []\n",
    "    for i in range(1,n-1):\n",
    "        A = combination_4(L[1:],k-1)\n",
    "        for e in A:\n",
    "            e_new = e+T\n",
    "            e_new.sort()\n",
    "            if not e_new in R: R.append(e_new)\n",
    "        T = [L[len(L)-1]]\n",
    "    return R\n",
    "\n",
    "combination_4([1,2,3,5,8],3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}