{VERSION 5 0 "IBM INTEL NT" "5.0" } {USTYLETAB {CSTYLE "Maple Input" -1 0 "Courier" 0 1 255 0 0 1 0 1 0 0 1 0 0 0 0 1 }{CSTYLE "2D Math" -1 2 "Times" 0 1 0 0 0 0 0 0 2 0 0 0 0 0 0 1 }{CSTYLE "Hyperlink" -1 17 "" 0 1 0 128 128 1 2 0 1 0 0 0 0 0 0 1 }{CSTYLE "2D Comment" 2 18 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 } {CSTYLE "" -1 25 "Courier" 0 1 0 0 0 1 2 2 0 0 0 0 0 0 0 1 }{CSTYLE " " -1 35 "" 0 1 104 64 92 1 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 36 "" 0 1 0 0 0 1 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 256 "" 0 1 0 0 0 0 0 0 2 0 0 0 0 0 0 0 }{CSTYLE "" -1 257 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 } {CSTYLE "" -1 258 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 259 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 260 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 261 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 262 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 263 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 264 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 265 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 266 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 267 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 268 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 269 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 270 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 271 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 272 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 273 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 274 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 275 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 276 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 277 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 278 "" 0 1 0 0 0 0 1 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 279 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 280 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 281 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 282 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 } {CSTYLE "" -1 283 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 284 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 285 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 286 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 287 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 288 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 289 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 290 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 291 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 292 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 293 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 294 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 295 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 296 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" 25 297 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 298 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 299 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 300 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 301 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 302 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 } {CSTYLE "" -1 303 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 304 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 305 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 306 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 307 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 } {CSTYLE "" -1 308 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 309 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 310 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 311 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 312 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 } {CSTYLE "" -1 313 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 }{CSTYLE "" -1 314 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 }{CSTYLE "" -1 315 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 }{CSTYLE "" -1 316 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 }{CSTYLE "" -1 317 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 } {CSTYLE "" -1 318 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 }{CSTYLE "" -1 319 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 }{CSTYLE "" -1 320 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 321 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 322 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 323 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 324 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 325 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 326 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 327 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 328 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 329 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 330 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 331 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 332 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 333 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 334 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 335 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 336 "" 0 1 0 0 0 0 1 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 337 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 338 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 339 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 340 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 341 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 342 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 343 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 344 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 345 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 346 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 347 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 348 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" 18 349 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" 18 350 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 351 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 352 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 353 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 354 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 355 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 356 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 357 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 358 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 359 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 360 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 361 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 362 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 363 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 364 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 365 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 366 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 367 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 368 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 369 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 370 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 371 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 372 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 373 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 374 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 375 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 376 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 377 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 378 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 379 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 380 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 381 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" 18 382 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 } {CSTYLE "" 18 383 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 384 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 385 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 386 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 387 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 388 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 389 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 390 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{PSTYLE "Normal" -1 0 1 {CSTYLE "" -1 -1 "Tim es" 1 12 0 0 0 1 2 2 2 2 2 2 1 1 1 1 }1 1 0 0 0 0 1 0 1 0 2 2 0 1 } {PSTYLE "Heading 1" -1 3 1 {CSTYLE "" -1 -1 "Times" 1 18 0 0 0 1 2 1 2 2 2 2 1 1 1 1 }1 1 0 0 8 4 1 0 1 0 2 2 0 1 }{PSTYLE "Heading 2" -1 4 1 {CSTYLE "" -1 -1 "Times" 1 14 0 0 0 1 2 1 2 2 2 2 1 1 1 1 }1 1 0 0 8 2 1 0 1 0 2 2 0 1 }{PSTYLE "List Item" -1 14 1 {CSTYLE "" -1 -1 "T imes" 1 12 0 0 0 1 2 2 2 2 2 2 1 1 1 1 }1 1 0 0 3 3 1 0 1 0 2 2 14 5 } {PSTYLE "Bullet Item" -1 15 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 0 1 2 2 2 2 2 2 1 1 1 1 }1 1 0 0 3 3 1 0 1 0 2 2 15 2 }{PSTYLE "Author" -1 19 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 0 1 2 2 2 2 2 2 1 1 1 1 }3 1 0 0 8 8 1 0 1 0 2 2 0 1 }{PSTYLE "Author" -1 256 1 {CSTYLE "" -1 -1 "Tim es" 1 14 0 0 0 1 2 1 2 2 2 2 1 1 1 1 }3 1 0 0 8 8 1 0 1 0 2 2 0 1 } {PSTYLE "Normal" -1 257 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 0 1 2 2 2 2 2 2 1 1 1 1 }3 1 0 0 0 0 1 0 1 0 2 2 0 1 }{PSTYLE "Normal" -1 258 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 0 1 2 1 2 2 2 2 1 1 1 1 }3 1 0 0 0 0 1 0 1 0 2 2 0 1 }{PSTYLE "Normal" -1 259 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 0 1 2 1 2 2 2 2 1 1 1 1 }1 1 0 0 0 0 1 0 1 0 2 2 0 1 } {PSTYLE "Title" -1 260 1 {CSTYLE "" -1 -1 "Times" 1 18 0 0 0 1 2 1 2 2 2 2 1 1 1 1 }3 1 0 0 12 12 1 0 1 0 2 2 19 1 }{PSTYLE "Normal" -1 261 1 {CSTYLE "" -1 -1 "Times" 1 14 0 0 0 1 2 1 2 2 2 2 1 1 1 1 }1 1 0 0 0 0 1 0 1 0 2 2 0 1 }} {SECT 0 {EXCHG {PARA 260 "" 0 "" {TEXT -1 10 "Lecture 12" }}{PARA 19 " " 0 "" {TEXT -1 0 "" }}}{SECT 1 {PARA 3 "" 0 "" {TEXT 256 39 "The RSA \+ Public Key Cryptographic System" }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 4 " The " }{TEXT 328 10 "RSA system" }{TEXT -1 6 " is a " }{TEXT 329 31 "p ublic-key cryptographic method" }{TEXT -1 78 " that permits both encry ption and digital signatures (authentication). Ronald " }{TEXT 351 1 " R" }{TEXT -1 11 "ivest, Adi " }{TEXT 352 1 "S" }{TEXT -1 19 "hamir, an d Leonard " }{TEXT 353 1 "A" }{TEXT -1 152 "dleman developed the RSA s ystem in 1977. RSA stands for the first letter in each of its invento rs' last names. For more information you may start with" }}{PARA 0 " " 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 7 " " }{TEXT 284 46 "http://www.rsasecurity.com/rsalabs/faq/3.html " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 67 "or you may do a web \+ luis search at the USF library on the key word " }{TEXT 285 12 "crypto graphy" }{TEXT -1 34 " for local books on the subject. " }}{PARA 0 " " 0 "" {TEXT -1 0 "" }}{PARA 261 "" 0 "" {TEXT -1 36 "Here's the way t he RSA system works:" }}}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 155 "Suppose Alice wants Bob to send her a secret m essage using the RSA system. Here's what she does. [The communication \+ can take place via email, for example.]" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 38 "1. She finds two large primes p and \+ q." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 47 "2. \+ She forms the product m = pq. We call m the " }{TEXT 286 7 "modulus" } {TEXT -1 3 ". \n" }}{PARA 0 "" 0 "" {TEXT -1 16 "3. She computes " } {XPPEDIT 18 0 "phi(m) = (p-1)*(q-1);" "6#/-%$phiG6#%\"mG*&,&%\"pG\"\" \"F+!\"\"F+,&%\"qGF+F+F,F+" }{TEXT -1 25 ". [This is the so-called " } {TEXT 331 18 "Euler phi function" }{TEXT -1 28 " applied to the modulu s m. ]" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 53 "4. She chooses a positive integer e such that igcd(e," }{XPPEDIT 18 0 "phi(m);" "6#-%$phiG6#%\"mG" }{TEXT -1 6 ") = 1." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 20 "5. She computes the " } {TEXT 287 7 "inverse" }{TEXT -1 18 ", call it d, of e " }{TEXT 288 6 " modulo" }{TEXT -1 1 " " }{XPPEDIT 18 0 "phi(m);" "6#-%$phiG6#%\"mG" } {TEXT -1 2 ".\n" }}{PARA 0 "" 0 "" {TEXT -1 92 "6. She sends the pair \+ of numbers [m,e] to Bob. This pair of numbers may be made public, but \+ " }{TEXT 257 11 "the numbers" }{TEXT -1 8 " p,q, d " }{TEXT 259 3 "and " }{TEXT -1 1 " " }{XPPEDIT 18 0 "phi(m);" "6#-%$phiG6#%\"mG" }{TEXT -1 1 " " }{TEXT 258 23 "should be kept secret! " }{TEXT -1 19 " We cal l [m,e] the " }{TEXT 261 10 "public key" }{TEXT -1 12 " and d, the " } {TEXT 262 11 "private key" }{TEXT -1 2 ". " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 106 "7. She tells Bob how to use Ma ple to convert the text of his message into a sequence of positive int egers " }{XPPEDIT 18 0 "a[1];" "6#&%\"aG6#\"\"\"" }{TEXT -1 3 " , " } {XPPEDIT 18 0 "a[2];" "6#&%\"aG6#\"\"#" }{TEXT -1 10 ", . . . , " } {XPPEDIT 18 0 "a[k];" "6#&%\"aG6#%\"kG" }{TEXT -1 51 " each less than \+ m. One such method is shown below. " }{TEXT 260 31 "This method can be made public." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 50 "8. She tells Bob to compute for each i the number " } {XPPEDIT 18 0 "b[i] = `mod`(a[i]^e,m);" "6#/&%\"bG6#%\"iG-%$modG6$)&% \"aG6#F'%\"eG%\"mG" }{TEXT -1 41 " and to send her the sequence of num bers " }{XPPEDIT 18 0 "b[1];" "6#&%\"bG6#\"\"\"" }{TEXT -1 2 ", " } {XPPEDIT 18 0 "b[2];" "6#&%\"bG6#\"\"#" }{TEXT -1 9 ", . . ., " } {XPPEDIT 18 0 "b[k];" "6#&%\"bG6#%\"kG" }{TEXT -1 23 ". He need not ke ep the " }{XPPEDIT 18 0 "b[i];" "6#&%\"bG6#%\"iG" }{TEXT -1 64 " 's se cret after he has computed them. But, he should keep the " }{XPPEDIT 18 0 "a[i];" "6#&%\"aG6#%\"iG" }{TEXT -1 10 "'s secret." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 27 "9. Now when Alice ge ts the " }{XPPEDIT 18 0 "b[i];" "6#&%\"bG6#%\"iG" }{TEXT -1 28 " 's fr om Bob, she computes " }{XPPEDIT 18 0 "`mod`(b[i]^d,m);" "6#-%$modG6$ )&%\"bG6#%\"iG%\"dG%\"mG" }{TEXT -1 34 " and this will turn out to be \+ the " }{XPPEDIT 18 0 "a[i];" "6#&%\"aG6#%\"iG" }{TEXT -1 96 "'s. Then \+ she can use Maple to convert these back into text as we illustrate in \+ the next section." }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}}{SECT 1 {PARA 3 "" 0 "" {TEXT -1 30 "Binary Exponentiation Modulo m" }}{PARA 0 "" 0 "" {TEXT -1 54 "A key component in implementing the RSA scheme \+ is the " }{TEXT 378 4 "fast" }{TEXT -1 17 " computation of " } {XPPEDIT 18 0 "`mod`(x^e,m);" "6#-%$modG6$)%\"xG%\"eG%\"mG" }{TEXT -1 111 " for large positive integers x, e, and m. An obvious, but infea sible, way to do this is to try the command :\n" }}{EXCHG {PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 10 "x^e mod m;" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 319 "The problem with this approach is that x^e is computed first. \+ If x and e are large, x^e may be larger than the number of particles \+ in the universe. So storing this number to divide it by m is not poss ible. For large enough integers x, m and e this may even cause Maple \+ to crash. Instead, one should use the command " }{TEXT 354 16 "Power( x,e) mod m" }{TEXT -1 49 ". This procedure implements an algorithm ca lled " }{TEXT 355 30 "binary exponentiation modulo m" }{TEXT -1 299 ". The basic idea is to perform a series of operations of the form y:=x ^2 mod m. This will give powers of the form x^N mod m where N is a po wer of 2. Some of these can be multiplied together to obtain x^e mod m . The algorithm is very simple, but amazingly efficient. One can see t he Maple code for " }{TEXT 379 16 "Power(x,e) mod m" }{TEXT -1 23 " (w hich is the same as " }{TEXT 380 19 "`mod/Power`(x,e,m) " }{TEXT -1 76 ") as follows. Aside from the error checking the procedure is quit e simple. " }}}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 54 "interface(verboseproc=3);\nprint(`mod/Power`);\nres tart:" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 39 "\n\nLet us compare the t ime required for " }{TEXT 356 9 "2^e mod m" }{TEXT -1 5 " and " } {TEXT 357 16 "Power(2,e) mod m" }{TEXT -1 5 " for " }{TEXT 381 4 "e = \+ " }{XPPEDIT 382 0 "2*10^6;" "6#*&\"\"#\"\"\"*$\"#5\"\"'F%" }{TEXT -1 5 " and " }{XPPEDIT 383 0 "m = 10^100+3;" "6#/%\"mG,&*$\"#5\"$+\"\"\" \"\"\"$F)" }{TEXT -1 40 ". If we tried to increase the value of " } {TEXT 384 1 "e" }{TEXT -1 71 " here we would quickly find that the fir st method would cause trouble.\n" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 23 "m:=10^100+3;\ne:=2*10^6;" }}}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 58 "st:=time():\na:=2^e mod m;\nelapsed_time:=(time()- \+ st)*sec;\n" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 66 "st:=time():\n b:=Power(2,e) mod m;\nelapsed_time:=(time()- st)*sec;\n\n" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 155 "\nUsing the first method for large e wil l be unfeasible, however, note how rapidly the binary exponentiation m ethod works for the following large integers:\n" }}}{EXCHG {PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 51 "die:=rand(1..10^100):\nx:=die();\ne:=die();\nm :=die();" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 68 "st:=time():\na: =Power(x,e) mod m:\nelapsed_time:=(time() - st)*sec;\na;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}}{SECT 1 {PARA 3 "" 0 "" {TEXT -1 30 "Illustration of the RSA System" }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 97 "We illustrate the RSA system using two randomly chosen primes w ith 20 decimal digits. Note that " }{XPPEDIT 18 0 "10^(n-1);" "6#)\"# 5,&%\"nG\"\"\"F'!\"\"" }{TEXT -1 46 " is the smallest n decimal digit integer and " }{XPPEDIT 18 0 "10^n-1;" "6#,&)\"#5%\"nG\"\"\"F'!\"\"" }{TEXT -1 93 " is the largest. For example if n = 3, we obtain the sm allest and largest 3 digit integers:\n" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "10^2; 10^3-1;" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 87 "We first generate two 20 digit random positive integers and then use \+ the Maple command " }{TEXT 332 9 "nextprime" }{TEXT -1 110 " to obtain the smallest primes greater than each number. Notice that in rand we \+ use the range 10^19..10^20-1.\n" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 55 "N:=rand(10^19..10^20 -1)();\nM:=rand(10^19..10^20 -1)();" }}} {EXCHG {PARA 0 "" 0 "" {TEXT -1 23 "Now we use the command " }{TEXT 385 9 "nextprime" }{TEXT -1 14 ". The command " }{TEXT 358 12 "nextpri me(n)" }{TEXT -1 41 " finds the smallest prime greater than n." }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 33 "p:=nextprime(N);\nq:=nextpri me(M);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 54 "Now we multiply these t wo primes together to form our " }{TEXT 333 7 "modulus" }{TEXT -1 3 " \+ m:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 7 "m:=p*q;" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 43 "How many digits does m have? This tells u s:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "length(m);" }}} {EXCHG {PARA 0 "" 0 "" {TEXT -1 15 "Now we compute " }{XPPEDIT 18 0 "p hi(m);" "6#-%$phiG6#%\"mG" }{TEXT -1 98 " which is possible since we k now that m = p*q where p and q are primes. We simply use the formula \+ " }{XPPEDIT 18 0 "phi(m) = (p-1)*(q-1);" "6#/-%$phiG6#%\"mG*&,&%\"pG\" \"\"F+!\"\"F+,&%\"qGF+F+F,F+" }{TEXT -1 30 ". [Note that this formula \+ for " }{XPPEDIT 18 0 "phi(m);" "6#-%$phiG6#%\"mG" }{TEXT -1 150 " work s only when m is a product of two different primes. If you study numbe r theory, you may learn more about this function.] We denote its valu e by " }{TEXT 359 4 "phi." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "phi:=(p-1)*(q-1);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 41 "Now we w ish to find a number e such that " }{XPPEDIT 18 0 "igcd(e,phi(m)) = 1; " "6#/-%%igcdG6$%\"eG-%$phiG6#%\"mG\"\"\"" }{TEXT -1 71 ". We keep tr ying random 20 digit integers till we find one that works." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 84 "for i from 1 do\ne:=rand(10^19..10^ 20-1)();\nif igcd(e,phi) = 1 then break; fi;\nod:\ne;" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 4 "The " }{TEXT 360 23 "inverse of e modulo p hi" }{TEXT -1 27 " is an integer d such that " }{TEXT 361 15 "e*d mod \+ phi = 1" }{TEXT -1 171 ". From number theory it is known that an integ er e has an inverse modulo phi if and only igcd(e,phi) = 1. The follo wing command will compute the inverse of e modulo phi:\n" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 15 "d:=1/e mod phi;" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 23 "\nWe check that e*d mod " }{XPPEDIT 18 0 "phi(m) " "6#-%$phiG6#%\"mG" }{TEXT -1 6 " = 1.\n" }}}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 12 "e*d mod phi;" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 7 "So the " }{TEXT 263 10 "public key" }{TEXT -1 41 " Alice sends to Bob and makes public is \n" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 " Public_Key:=[m,e];" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 54 "\nThe infor mation we must keep secret in this case is:\n" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 25 "Private_key:=[p,q,d,phi];" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 18 "\nIn cryptography, " }{TEXT 265 10 "plain text" } {TEXT -1 77 " refers to any message that is not enciphered. After encr yption it is called " }{TEXT 266 11 "cipher text" }{TEXT 362 2 ". " } {TEXT -1 46 "We assign Bob's message to the variable named " }{TEXT 289 10 "plain_text" }{TEXT -1 70 ", as follows. (Of course, the name o f the variable is not important.)\n" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 275 "plain_text:=\"It is not knowledge, but the act of le arning, not possession but the act of getting there, which grants the \+ greatest enjoyment. When I have clarified and exhausted a subject, the n I turn away from it, in order to go into darkness again; --Karl Frie drich Gauss\";\n" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 216 "Note that th e text includes new line symbols, \\n, as well as numerous blanks.The \+ \\ at the end of each line is just Maple's way of saying that this sho uld all be on one line, but I am forced to break it at this point." }} }{EXCHG {PARA 0 "" 0 "" {TEXT -1 74 "\nWe now convert this text to a l ist of numbers each in the range 0 to 255:" }}}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 33 "List1:=convert(plain_text,bytes);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 109 "We consider List1 as the base 256 representati on of a number. We convert this to a base m number as follows:" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 34 "List2:=convert(List1,base, 2 56,m);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 37 "Now we apply the mappin g which sends " }{TEXT 363 1 "x" }{TEXT -1 4 " to " }{TEXT 364 16 "Pow er(x,e) mod m" }{TEXT -1 20 " to each number in " }{TEXT 334 5 "List2 " }{TEXT -1 25 ". This can be done using " }{TEXT 264 5 "map. " } {TEXT -1 67 " We thus obtain the enciphered message that will be sent \+ to Alice. " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 45 "cipher_text:=map(x->Power(x,e) mod m, List2);" }}} {EXCHG {PARA 0 "" 0 "" {TEXT -1 116 "\nNow Bob sends this to Alice and the whole world for that matter. But since only Alice has the secret \+ private key, " }{TEXT 290 45 "only she will be able to decipher the m essage" }{TEXT -1 61 " (in the case where p and q are chosen with suff icient care.)" }}{PARA 0 "" 0 "" {TEXT -1 80 "\nWe show now how she de ciphers the message: She applies the mapping which sends " }{TEXT 365 1 "x" }{TEXT -1 4 " to " }{TEXT 366 16 "Power(x,d) mod m" }{TEXT -1 7 " where " }{TEXT 367 1 "d" }{TEXT -1 44 " is her private key to each r eceived number:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 48 "decipher 1:=map(x->Power(x,d) mod m,cipher_text);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 35 "Next she converts this to base 256:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 41 "decipher2:=convert(decipher1,base,m,256);" }} }{EXCHG {PARA 0 "" 0 "" {TEXT -1 81 "Finally she converts the numbers \+ back to text and sees what message Bob sent her:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 36 "decipher3:=convert(decipher2,bytes);" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}}{SECT 1 {PARA 3 "" 0 " " {TEXT -1 23 "Breaking the RSA System" }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 30 "To decipher the message it is " }{TEXT 335 8 "believed" } {TEXT -1 112 " (but not proved) that one must be able to find the priv ate key d given only the public key [m,e]. If one knows " }{XPPEDIT 18 0 "phi(m);" "6#-%$phiG6#%\"mG" }{TEXT -1 54 " then Maple quickly co mputes d by the command 1/e mod " }{XPPEDIT 18 0 "phi(m);" "6#-%$phiG6 #%\"mG" }{TEXT -1 30 ". It is known that computing " }{XPPEDIT 18 0 " phi(m);" "6#-%$phiG6#%\"mG" }{TEXT -1 733 " is the same order of diffi culty as factoring m. If m is the product of two 100 digit primes, say , then m is 200 digits long and current factoring algorithms are unabl e to factor such numbers within a reasonable time unless the primes ar e poorly chosen (as in Problem 4 in this week's homework assignment). \+ Don't ask Maple to factor such a number for you unless you want to wa it a long time -- years or centuries, depending on the size of the num ber and luck. Factoring algorithms always depend on luck. After all on e might guess the factors, but this would be very unlikely. Of course, the technology is changing rapidly. Mathematicians are finding better algorithms and Engineers are building faster computers every day it s eems. " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 11 "It is also " }{TEXT 269 8 "believed" }{TEXT -1 184 " (but not proved) that breaking the RSA system is equivalent to factoring the modulus m . The best algorithm known at present for factoring such large, diffic ult numbers, is called the " }{TEXT 270 38 "Number Field Sieve Factori ng Algorithm" }{TEXT -1 35 ". A group of mathematicians called " } {TEXT 267 9 "The Cabal" }{TEXT -1 79 " announced the completion, on No vember 14, 2000, of the factorization with the " }{TEXT 268 33 "Specia l Number Field Sieve (SNFS)" }{TEXT -1 36 " of the 233-digit Cunningha m number " }{XPPEDIT 18 0 "2^773+1;" "6#,&*$\"\"#\"$t(\"\"\"F'F'" } {TEXT -1 748 " into the product of the numbers 3 and 533371 and three \+ primes of 55, 71, and 102 digits, respectively. This established a ne w record for the Special Number Field Sieve. [Note that this is somew hat easier to factor than a number of this size which is the product o f only two primes of approximate equal size. In this case the 3 and 5 33371 factors were easy to find, and the remaining factor has the \"sm all\" 55-digit and 71-digit primes.] \n\nThe sieving was done on about 150 SGI workstations and Sun workstations and servers running at 180- 450 MHz, and on about 100 PCs running at 266-600 MHz. The sieving took about five calendar months. It was started mid-April, 2000, and finis hed on September 15, 2000. Total sieving time was 57.4 CPU years. " }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 67 "For more \+ information on factoring and the RSA scheme take a look at" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 4 " " }{TEXT 368 64 "http://www.rsasecurity.com/rsalabs/challenges/factoring/faq.html" }}{PARA 0 "" 0 "" {TEXT -1 29 "\nHere you can read about the " }{TEXT 369 23 "RSA Factoring Challenge" }{TEXT -1 660 ", an effort, sponsored by RSA Laboratories, to encourage research into the factoring of larg e numbers of the type used in RSA keys. A set of eight challenge numbe rs, ranging in size from 576 bits to 2048 bits is posted here. Each nu mber is the product of two large primes, similar to the modulus of an \+ RSA key pair. Prize awards from $10,000 to $200,000 are offered for th e prime factors of these eight numbers.\n\nThere are many sources of i nformation on the RSA system. It is important not only for sending dat a securely but also can be used to \"sign\" electronically submitted d ocuments. For more information see for example any of the many books a vailable on " }{TEXT 271 14 "cryptography. " }{TEXT -1 81 " Just searc h on this key word using Web Luis or on your favorite search engine. \+ " }{TEXT 272 21 "RSA Data Security Inc" }{TEXT -1 51 ". now controls t he RSA system. The company's URL is" }{TEXT 273 1 " " }}{PARA 0 "" 0 " " {TEXT -1 1 " " }}{PARA 0 "" 0 "" {TEXT 370 36 " http://www.rsa security.com/. " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 5 "Both " }{TEXT 371 8 "Netscape" }{TEXT -1 5 " and " }{TEXT 372 17 "Internet Explorer" }{TEXT -1 64 " contain security software fr om RSA Data Security Inc. Also the " }{TEXT 337 3 "PGP" }{TEXT -1 226 " (Pretty Good Privacy) encryption system incorporates the RSA scheme. PGP can be used for authentication purposes (i.e., to electronically sign a document). You may download the program for free from the MIT \+ website\n\n " }{TEXT 373 35 "http://web.mit.edu/network/pgp.htm l" }{TEXT 336 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 123 "You may find out about Philip Zimmermann, the creator of PGP, and his troubles with the government at his webpage\n\n \+ " }{TEXT 374 23 "http://web.mit.edu/prz/" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 124 "He even has his phone number give n on the webpage, but in a way that forces people to read an entire pa ragraph to obtain it." }}{PARA 0 "" 0 "" {TEXT -1 1 "\n" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}}{SECT 1 {PARA 3 "" 0 "" {TEXT -1 31 " readdata, writeto and appendto" }}{PARA 0 "" 0 "" {TEXT -1 0 " " }}{PARA 0 "" 0 "" {TEXT -1 553 "If one wants to run a Maple program \+ that will take several days to complete the computation and that requi res that data be printed out along the way, it is wise to print this t o a file. This way if Maple crashes before it finished, at least some \+ data can be obtained from the file. Also there are times when you migh t obtain data from other sources that you wish Maple to process. In th is case if the data is in a text file, it may be read into a Maple wor ksheet so that you can process it further. Here are some commands that will allow one to do this." }}{SECT 1 {PARA 4 "" 0 "" {TEXT -1 20 "wr iteto and appendto" }}{EXCHG {PARA 15 "" 0 "" {TEXT -1 17 "When the co mmand " }{TEXT 291 18 "writeto(filename);" }{TEXT -1 79 " is executed \+ all future commands will have their results immediately stored in " } {TEXT 338 8 "filename" }{TEXT -1 129 " and will not be displayed on th e screen. Unless you indicate otherwise the file will be created and s tored in your Maple folder." }}{PARA 15 "" 0 "" {TEXT -1 115 "While in this mode, no prompt will appear at the terminal. The prompt and the \+ input statements will be echoed into " }{TEXT 339 8 "filename" }{TEXT -1 33 " (unless echoing is turned off). " }}{PARA 15 "" 0 "" {TEXT -1 20 "The special command " }{TEXT 292 17 "writeto(terminal)" }{TEXT -1 73 " will restore the standard mode of printing the results on the ter minal. " }}{PARA 15 "" 0 "" {TEXT -1 3 "If " }{TEXT 340 8 "filename" } {TEXT -1 58 " already exists the contents of the file are overwritten. " }}{PARA 15 "" 0 "" {TEXT -1 62 "An alternative mode of writing to a file is available via the " }{TEXT 294 8 "appendto" }{TEXT -1 26 " fu nction. In the case of " }{TEXT 293 19 "appendto(filename);" }{TEXT -1 50 " rather than overwriting the contents (if any) of " }{TEXT 341 8 "filename" }{TEXT -1 20 ", the new output is " }{TEXT 343 8 "appende d" }{TEXT -1 4 " to " }{TEXT 342 8 "filename" }{TEXT -1 21 ". In other respects, " }{TEXT 295 8 "appendto" }{TEXT -1 5 " and " }{TEXT 296 7 "writeto" }{TEXT -1 288 " have the same functionality. \nOn a Windows \+ machine the file name must include location of the file. In particular backslashes appearing in a file name (these being used as a director y separator character on Windows machines) must be escaped by \"doubli ng up.\" For example, the file name " }{TEXT 35 27 "C:\\Maple\\Workshe ets\\Buffied" }{TEXT -1 20 " must be written as " }{TEXT 35 32 "\"C:\\ \\Maple\\\\Worksheets\\\\Buffied\"" }{TEXT -1 48 ". Alternatively, you can use the canonical form " }{TEXT 35 29 "\"C:/Maple/Worksheets/Buff ied\"" }}{PARA 0 "" 0 "" {TEXT -1 47 "To see what's going on we will n eed to use the " }{TEXT 344 8 "readdata" }{TEXT -1 9 " function" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "restart;" }}}{EXCHG {PARA 0 " " 0 "" {TEXT -1 229 "We will place the data in the file named datafile 1 on the Desktop using the following command. After the following writ eto command everything will be printed to the file named datafile1 and no output will appear in the worksheet." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 65 "writeto(\"C:\\\\Documents and Settings\\\\Owner\\\\De sktop\\\\datafile1\");" }{TEXT -1 2 " \n" }{MPLTEXT 1 0 98 "for i from 10^10 to 10^10 + 6 do\nprintf(\"%15d %15d %15d \\n\",i, 5*i, 10*i);\n od;\nwriteto(terminal); " }{TEXT -1 71 "This causes output to be print ed in the worksheet and not in datafile1." }}}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 0 "" }}}}{SECT 1 {PARA 4 "" 0 "" {TEXT -1 8 "readdata" }}{PARA 15 "" 0 "" {TEXT -1 4 "The " }{TEXT 297 9 "readdata " }{TEXT -1 341 "function reads numeric data from an input text file into Maple . The data must consist of integers or floats arranged in columns sepa rated by white space. If only one column of data is read, the output i s a list of the data. If more than one column is read, the output is a list of rows of data corresponding to the rows of data in the file. \+ " }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 81 "L:=readdata(\"C:\\\\Docu ments and Settings\\\\Owner\\\\Desktop\\\\datafile1\", integer, 3);" } }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 46 "Here are two ways to display the date read in." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "Matrix(L) ;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 71 "for i from 1 to nops(L ) do \nprintf(\" %15d %15d %15d \\n\",op(L[i])); \nod;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}}}{SECT 1 {PARA 3 "" 0 "" {TEXT -1 81 "More read and write commands (Those not interested may sa fely skip this section.)" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 175 "Maple has a variety of commands for read ing data from external files and writing data to external files. The t ype of command you use depends on the type of data. For example, " } {TEXT 308 8 "readdata" }{TEXT -1 51 " will work for lists of numbers, \+ but you will need " }{TEXT 309 8 "readline" }{TEXT -1 15 " to read tex t (" }{TEXT 310 7 "strings" }{TEXT -1 168 "). Similarly for writing to a file, the type of data is important. Here is a brief summary of the other commands. For more details see the online help for each command ." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 311 10 "For input:" }{TEXT -1 5 "\n\n1. " }{TEXT 298 8 "readline" }{TEXT -1 65 " \+ reads a single line from a file or the terminal, and returns it " } {TEXT 314 11 "as a string" }{TEXT -1 94 ". You can then parse this wi th \"sscanf\" or the \"parse\" function (for Maple expressions).\n\n2. " }{TEXT 299 8 "readdata" }{TEXT -1 19 " reads a text file " }{TEXT 313 18 "containing numbers" }{TEXT -1 149 " separated by tabs or space s, and returns it as a list. You can specify which columns to read, a nd whether to treat them as integers or floats.\n\n3. " }{TEXT 300 26 "fscanf , sscanf, and scanf" }{TEXT -1 150 " are based on the C standa rd library functions of the same names for formatting input. The Mapl e versions of these functions each return a list.\n\n4. " }{TEXT 301 9 "readbytes" }{TEXT -1 29 " reads a specified number of " }{TEXT 315 5 "bytes" }{TEXT -1 80 " from a file, and returns either a list of int egers or a string of characters.\n\n" }{TEXT 312 11 "For output:" } {TEXT -1 5 "\n\n1. " }{TEXT 302 9 "writeline" }{TEXT -1 8 " writes " } {TEXT 316 8 "strings " }{TEXT -1 31 "to a file or the terminal.\n\n2. \+ " }{TEXT 303 9 "writedata" }{TEXT -1 18 " is used to write " }{TEXT 317 14 "numerical data" }{TEXT -1 21 " to a text file.\n\n3. " }{TEXT 304 29 "fprintf , sprintf, and printf" }{TEXT -1 198 " are based on th e C standard library functions of the same names; these allow you to c ontrol the format of output. There is also an \"nprintf\" which retur ns a Maple symbol rather than a string.\n\n4. " }{TEXT 305 10 "writeby tes" }{TEXT -1 12 " writes the " }{TEXT 318 5 "bytes" }{TEXT -1 120 " \+ from a string of characters or list of integers to a file (the file is opened with type text or binary, respectively).\n" }}{PARA 0 "" 0 "" {TEXT -1 3 "5. " }{TEXT 306 7 "writeto" }{TEXT -1 4 " or " }{TEXT 307 8 "appendto" }{TEXT -1 8 " writes " }{TEXT 319 22 "output from the scr een" }{TEXT -1 41 " into the specified file. In the case of " }{TEXT 320 8 "writeto," }{TEXT -1 45 " the old file is overwritten, in the ca se of " }{TEXT 321 9 "appendto," }{TEXT -1 65 " the new data produced \+ by Maple is appended to the existing file." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}}{SECT 1 {PARA 3 "" 0 "" {TEXT -1 41 "Converting to Fortran, C, Latex, and HTML " }}{PARA 0 "" 0 "" {TEXT -1 5 "\nThe " }{TEXT 35 7 "fortran" }{TEXT -1 69 " function generates Fortran code for evaluating the input. The \+ input " }{TEXT 35 1 "s" }{TEXT -1 107 " must be a single algebraic exp ression, an array of algebraic expressions, a list of equations of the form " }{TEXT 35 16 "name = algebraic" }{TEXT -1 86 " that is underst ood to mean a sequence of assignment statements, or a Maple procedure. " }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 22 "with(codegen,fortran):" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 48 "f:=unapply(sin(x*y) + ln( x^2 + 5*x*y + 1), x,y);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 11 " fortran(f);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 4 "The " }{TEXT 35 1 " C" }{TEXT -1 63 " function generates C code for evaluating the input. \+ The input " }{TEXT 35 1 "s" }{TEXT -1 129 " must be one of the followi ng: a single algebraic expression, an array of algebraic expressions, \+ a list of equations of the form " }{TEXT 35 16 "name = algebraic" } {TEXT -1 89 " (which is understood to mean a sequence of assignment st atements), or a Maple procedure." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "with(codegen,C):" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 5 "C(f);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 1 "\n " }{TEXT -1 4 "The " }{TEXT 322 5 "latex" }{TEXT -1 85 " function prod uces output which is suitable for printing the input expression with a " }{TEXT 323 8 "LaTeX 2e" }{TEXT -1 298 " processor. It knows how to \+ format integrals, limits, sums, products and matrices. If you use late x you may find it useful to generate matrices and other objects with M aple. Use the following to generate latex code and then copy and paste it into your latex document. Here are a couple of examples:" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 47 "A:=matrix([[seq(i,i=1..5)],[ seq(i^2,i=1..5)]]);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 9 "latex (A);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 28 "B:=Int(x^2*cos(x)*e xp(x),x);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 9 "latex(B);" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 3 "To " }{TEXT 324 6 "export" }{TEXT -1 19 " a worksheet as a n " }{TEXT 325 4 "HTML" }{TEXT -1 40 " document for viewing in a Web b rowser: " }}{PARA 14 "" 0 "" {TEXT -1 48 " 1. Open the worksheet that \+ you want to export. " }}{PARA 14 "" 0 "" {TEXT -1 13 " 2. From the " } {TEXT 36 4 "File" }{TEXT -1 14 " menu, choose " }{TEXT 36 9 "Export As " }{TEXT -1 11 ", and then " }{TEXT 36 4 "HTML" }{TEXT -1 87 ". \n\nNo te that when Maple creates the HTML file it will also create a folder \+ containing " }{TEXT 386 3 "gif" }{TEXT -1 59 " files that will be empl oyed when the HTML file is opened. " }}{PARA 14 "" 0 "" {TEXT -1 0 "" }}{PARA 14 "" 0 "" {TEXT -1 599 "You may use the above to convert the \+ entire worksheet to an HTML file. Or, individual plots can be saved i n a separate worksheet and then exported to html. This will create a f ile containing only the plot. The animated plots will run continuously when opened with a web browser. \n\nTo how this works: execute the th e following animation. Then select the output of the animation. Open a new worksheet and paste it into the new worksheet. Then follow the ab ove instructions to export as an html document. Note that this will al so create a gif file which will be placed in a some folder usually cal led " }{TEXT 387 6 "images" }{TEXT -1 117 ". After you have done this \+ open the html file with Netscape or Internet Explored and you will se e a \"flying plane\". " }}{PARA 14 "" 0 "" {TEXT -1 0 "" }}{PARA 14 " " 0 "" {TEXT -1 44 "If you want to experiment you may go to the " } {TEXT 376 4 "File" }{TEXT -1 19 " menu item, select " }{TEXT 375 7 "Sa ve As" }{TEXT -1 51 ", and when the window comes up choose for filetyp e " }{TEXT 377 11 "HTML Source" }{TEXT -1 73 ". This will save the ent ire worksheet. You can open it with a webbrowser." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 86 "plots[anima te3d]( 10*sin(t)*abs(y)*abs(x), x = -1..1,y=-3..3, t=0..2*Pi, style=pa tch);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}}{SECT 1 {PARA 3 "" 0 "" {TEXT -1 28 "Writing Efficient Maple Code" }}{PARA 0 " " 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 215 "For a number of u seful hints on how to write efficient code, that is, how to improve th e performance of a program that you have working, but would like to sp eed up, read the help page that comes up when you execute " }{TEXT 330 10 "?efficient" }{TEXT -1 56 ". Here are a couple of paragraphs f rom this help page. " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 " " {TEXT -1 61 "Use the correct routine for the job. For example, do no t use " }{TEXT 35 3 "sum" }{TEXT -1 4 " or " }{TEXT 35 4 "prod" } {TEXT -1 6 " when " }{TEXT 35 3 "add" }{TEXT -1 4 " or " }{TEXT 35 3 " mul" }{TEXT -1 101 " is adequate. Computing integrals numerically shou ld be done by evaluating an expression of the form " }{TEXT 35 20 "eva lf( Int( expr ) )" }{TEXT -1 41 ", which uses the inert integral opera tor " }{TEXT 35 3 "Int" }{TEXT -1 23 ", rather than by using " }{TEXT 35 20 "evalf( int( expr ) )" }{TEXT -1 59 ", which first attempts to c ompute the symbolic integral of " }{TEXT 35 4 "expr" }{TEXT -1 77 ". C omputational linear algebra can be most efficiently done by using the \+ new " }{HYPERLNK 17 "LinearAlgebra" 2 "LinearAlgebra" "" }{TEXT -1 20 " package; avoid the " }{HYPERLNK 17 "linalg" 2 "linalg" "" }{TEXT -1 64 " package for numerically intensive linear algebra computations. " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 15 "Avoid e xplicit " }{TEXT 35 3 "do " }{TEXT -1 329 "loops. Most uses of loops i n Maple can be replaced by calls to very fast (built-in) procedures th at perform an iteration. If you need to construct an expression sequen ce (including sets, lists, sums, and products), avoid iteratively buil ding the sequence by appending to it. Consider using any of the follow ing commands instead: " }{TEXT 388 35 "seq, map, map2, fold1, zip, sel ect," }{TEXT -1 5 " and " }{TEXT 389 6 "remove" }{TEXT -1 1 "." }} {PARA 0 "" 0 "" {TEXT -1 89 "There are cases, however, when a loop can be faster than a corresponding built-in routine" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 84 "If you want more advice o n writing efficient programs execute the following command." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "?e fficient" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}}{SECT 1 {PARA 3 "" 0 "" {TEXT -1 36 "Assignment 12 -- Tuesday, December 3" }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{EXCHG {PARA 0 "" 0 "" {TEXT 274 10 "P roblem 1." }{TEXT -1 98 " Alice sent a message to Bob using the RSA s ystem. The public key used to encode the message was " }}{PARA 0 "" 0 "" {TEXT -1 79 "[m,e] = [187454749788911503119994043213682616233000961 , 23073697474256143563]. " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 " " 0 "" {TEXT -1 26 "The enciphered message was" }}{PARA 0 "" 0 "" {TEXT -1 1 " " }}{PARA 0 "" 0 "" {TEXT -1 1228 " [99763088506717050716 379498520357841718875740, 12016541376842511231133708519128228602051544 2, 130554852152844850464253187688342192964186591, 30831038803473309186 944039044693095063005267, 43791870977158745785820581340119798552660187 , 69969965042359538654291028155927734707714502, 3386996592569999090380 1791477929460546990002, 33844215332363231914638130818590411552396086, \+ 61034870951899306892357141802983347226683758, 152680702248950827958295 294572717135277913525, 109591116592896191360922558098912453060002989, \+ 155489947789995346755966254731407091292570943, 30508537854841352888337 386800131678916944679, 45657204694505066046067342403378233363404150, 1 22580283375455701674982424288406984864898071, 631906457183520161048246 79398188140019415424, 17253386795565064409576412640690151622064852, 76 432681365602448262013510061731737725777808, 44198551234698976690960671 67819380964828479, 87913005918401414546998775379426321338719933, 15543 4516526735215629181544556450169276890711, 7469538135990111444316886690 5755723039288800, 246854149837977729662442017899408430336317, 12176622 7774612543867361050340041336298158533, 1667843520800966335240335633648 25999607054575, 72405993088552642775735865911360107823805504]\n\nDecip her this message. " }{TEXT 345 4 "Hint" }{TEXT -1 9 ". Use of " } {TEXT 390 7 "ifactor" }{TEXT -1 37 " with the option 'pollard' may hel p. " }{TEXT 346 112 "When you are finished with the decryption. You sh ould use colons where possible to suppress unnecessary output. " } {TEXT -1 2 "\n\n" }{TEXT 275 10 "Problem 2." }{TEXT -1 176 " Find, us ing Maple, a triple [m,e,d] where m is the product of two 200 decimal \+ digit primes, e is a random prime number of 100 decimal digits and d i s the inverse of e modulo " }{XPPEDIT 18 0 "phi(m);" "6#-%$phiG6#%\"mG " }{TEXT -1 215 ". Use this to encipher some message of your choice of at least 6 lines length using the RSA system. You may copy and paste \+ text from some website. Then, decipher the enciphered text to obtain t he original message.\n\n" }{TEXT 276 9 "Problem 3" }{TEXT -1 55 ". Giv en that m = pq where p and q are primes and that " }{XPPEDIT 18 0 "ph i(m) = (p-1)*(q-1);" "6#/-%$phiG6#%\"mG*&,&%\"pG\"\"\"F+!\"\"F+,&%\"qG F+F+F,F+" }{TEXT -1 15 ". Suppose that " }{XPPEDIT 18 0 "m = 10^100+59 8*10^50+67497;" "6#/%\"mG,(*$\"#5\"$+\"\"\"\"*&\"$)fF)*$F'\"#]F)F)\"&( \\nF)" }{TEXT -1 6 " and " }{XPPEDIT 18 0 "phi(m) = 10^100+596*10^50+ 66900;" "6#/-%$phiG6#%\"mG,(*$\"#5\"$+\"\"\"\"*&\"$'fF,*$F*\"#]F,F,\"& +p'F," }{TEXT -1 69 ". Find p and q. Check that the factors you find \+ are indeed primes.\n\n" }{TEXT 327 6 "Hint: " }{TEXT -1 41 "You have t wo equations and two unknowns. " }}{PARA 0 "" 0 "" {TEXT -1 1 "\n" } {TEXT 277 9 "Problem 4" }{TEXT -1 232 ". [This exercise shows that if \+ care is not taken in choosing the primes p and q used in the RSA syste m that the system can be easily broken.] Suppose you know that a pers on's public key modulus m is the following 200 digit number :" }} {PARA 0 "" 0 "" {TEXT -1 1 " " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "" 0 "" {XPPEDIT 18 0 "166571820085905498772938593207359906487 3157741565141450895641346700924767530822922357350877372991440872474774 9233779284765414625308352967639300872282279199825030962210816740376886 176930271167988018683;" "6#\"cw$o=!))z;r-$p<')oPSn\"3@i4.D)*>zAGs3IRw' HN3`i9aw%GzPB\\xuC(3W\"*HPx3NdB#H#3`nZ#4qY8k&*3XT^cTx:t[1*ft?$fQHx)\\0 f3?=dm\"" }{TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 326 65 "Factor m and check \+ your factorization after the factors are found" }{TEXT -1 3 ". " } {TEXT 281 18 "Use the following " }{TEXT 278 27 "Fermat factorization \+ method" }{TEXT 282 2 ": " }{TEXT -1 15 " Note that if " }{XPPEDIT 18 0 "m = x^2-y^2;" "6#/%\"mG,&*$%\"xG\"\"#\"\"\"*$%\"yGF(!\"\"" }{TEXT -1 6 " then " }{XPPEDIT 18 0 "m = (x-y)*(x+y);" "6#/%\"mG*&,&%\"xG\"\" \"%\"yG!\"\"F(,&F'F(F)F(F(" }{TEXT -1 8 ". So if " }{XPPEDIT 18 0 "1 < x-y;" "6#2\"\"\",&%\"xGF$%\"yG!\"\"" }{TEXT -1 198 " we have a non-tr ivial factorization of m. If m is a product of just two primes then on e will be x - y and the other will be x + y. This is the basis of the Fermat factorization method. Note that " }{XPPEDIT 18 0 "m = x^2-y^2 " "6#/%\"mG,&*$%\"xG\"\"#\"\"\"*$%\"yGF(!\"\"" }{TEXT -1 18 " is equiv alent to " }{XPPEDIT 18 0 "x^2-m = y^2;" "6#/,&*$%\"xG\"\"#\"\"\"%\"mG !\"\"*$%\"yGF'" }{TEXT -1 35 ". So if for some number x we have " } {TEXT 279 34 "type(sqrt(x^2 - m),integer) = true" }{TEXT -1 17 " then \+ we can set " }{TEXT 347 18 "y = sqrt(x^2 - m) " }{TEXT -1 70 "and usin g the above idea we may factor m. Fermat's method is to take " } {TEXT 348 4 "x = " }{XPPEDIT 349 0 "ceil(sqrt(m));" "6#-%%ceilG6#-%%sq rtG6#%\"mG" }{TEXT -1 59 " and keep incrementing x by 1 till an x is f ound such that " }{XPPEDIT 350 0 "x^2-m;" "6#,&*$%\"xG\"\"#\"\"\"%\"mG !\"\"" }{TEXT -1 12 " is a square" }{TEXT 280 3 ". " }{TEXT -1 1 " " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 31 "[Note t hat you may need to use " }{TEXT 283 24 "ceil(evalf(sqrt(m),200))" } {TEXT -1 3 ".] " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 271 "If the number m is a product of two primes that are rela tively close together then this method will factor m quickly. If you d o not find the factors in just a few seconds, you probably have a bug \+ in your program. For some reason Maple does not have this method built in. \n" }}}}}{MARK "9 0 0" 36 }{VIEWOPTS 0 0 0 1 1 1803 1 1 1 1 } {PAGENUMBERS 1 1 1 33 1 1 }