25 people like it.
Like the snippet!

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 Head : '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

Raw view Test code New version

More information

Link:	http://fssnip.net/20
Posted:	13 years ago
Author:	Natallie Baikevich
Tags:	rsa , euler problem , gcd , recursion , sumby