 25 people like it.

# Project Euler #182

The RSA encryption is based on the following procedure: Generate two distinct primes p and q. Compute n=pq and phi=(p-1)(q-1). Find an integer e, 1

 ``` 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: 28: 29: 30: 31: 32: 33: 34: 35: 36: 37: 38: 39: 40: 41: 42: 43: 44: 45: 46: 47: ``` ``````///Simple gcd with ifs ///Nice moment: all recs there transform to whiles. let rec gcd a b = if b = 0L then a else gcd b (a % b) (Simple gcd with match) ///Binary gcd with match let rec gcdBin a b = match a, b with |0L, _ |_, 0L -> a ||| b |_ when (a &&& 1L) ||| (b &&& 1L) = 0L -> gcdBin (a >>> 1) (b >>> 1) <<< 1 |_ when a &&& 1L = 0L -> gcdBin (a >>> 1) b |_ when b &&& 1L = 0L -> gcdBin a (b >>> 1) |_ when a > b -> gcdBin ((a - b) >>> 1) b |_ -> gcdBin ((b - a) >>> 1) a (Binary gcd with ifs) (* The minimum number of unconcealed messages is (1 + gcd (e-1) (q-1)) * (1 + gcd (e-1) (p-1)) = 9 So the gcds there should be equal to 2 *) let sum p q = let phi = (p - 1L) * (q - 1L) in [3L..2L..phi - 1L] //Realization using filter is maybe more beautiful, but less efficient |> List.sumBy (fun e -> if gcd e phi = 1L && gcd (e - 1L) (q - 1L) = 2L && gcd (e - 1L) (p - 1L) = 2L then e else 0L) printfn "%A" <| sum 1009L 3643L //399788195976L (* The gcd test for 10000 random values says 'Be simple!': simple gcd + if: 00.0058234 binary gcd + if: 00.0066124 binary gcd + match: 00.0067200 simple gcd + match: 00.0067880 *) ``````
val gcd : a:int64 -> b:int64 -> int64

Full name: Script.gcd

Simple gcd with ifs
Nice moment: all recs there transform to whiles.
val a : int64
val b : int64
let rec gcd' a b =
match b with
|0L -> a
|_ -> gcd' b (a % b)
val gcdBin : a:int64 -> b:int64 -> int64

Full name: Script.gcdBin

Binary gcd with match
let rec gcdBin' a b =
if a = 0L || b = 0L then a ||| b
else if (a &&& 1L) ||| (b &&& 1L) = 0L then
gcdBin' (a >>> 1) (b >>> 1) <<< 1
else if a &&& 1L = 0L then gcdBin' (a >>> 1) b
else if b &&& 1L = 0L then gcdBin' a (b >>> 1)
else if a > b then gcdBin' ((a - b) >>> 1) b
else gcdBin' ((b - a) >>> 1) a
val sum : p:int64 -> q:int64 -> int64

Full name: Script.sum
val p : int64
val q : int64
val phi : int64
Multiple items
module List

from Microsoft.FSharp.Collections

--------------------
type List<'T> =
| ( [] )
| ( :: ) of Head: 'T * Tail: 'T list
interface IEnumerable
interface IEnumerable<'T>
member IsEmpty : bool
member Item : index:int -> 'T with get
member Length : int
member Tail : 'T list
static member Cons : head:'T * tail:'T list -> 'T list
static member Empty : 'T list

Full name: Microsoft.FSharp.Collections.List<_>
val sumBy : projection:('T -> 'U) -> list:'T list -> 'U (requires member ( + ) and member get_Zero)

Full name: Microsoft.FSharp.Collections.List.sumBy
val e : int64
val printfn : format:Printf.TextWriterFormat<'T> -> 'T

Full name: Microsoft.FSharp.Core.ExtraTopLevelOperators.printfn