Overclock.net banner
21 - 40 of 99 Posts

·
Premium Member
Joined
·
2,687 Posts
Quote:


Originally Posted by Manyak
View Post

out of all the programming languages out there, LISP was one of the last ones I expected to see in this thread - right down there with BCPL


Lisp/Scheme is really a fun language if you take the time to learn it. It may look a little odd with all the parentheses, but once you get past that it begins to look really beautiful.
 

·
Registered
Joined
·
1,198 Posts
Quote:


Originally Posted by Manyak
View Post

There exist values of e and m such that me mod n=m.
We call messages m for which me mod n=m unconcealed messages.

I think you should fix:

Quote:


me mod n=m

to:

Quote:


m^e mod n=m

or

Quote:


m^e ≣ m (mod n)

It took me hours to understand what you mean, and I now understand how directly unconcealed was used, unconcealed is used as a synonym of unchanged.

PS. After hours of thinking, the only way I found to check every possible e and every possible m for this e. That's why I'll try to do it in C, but some other day.
 

·
Premium Member
Joined
·
11,951 Posts
Discussion Starter · #23 ·
Quote:


Originally Posted by metala
View Post

I think you should fix:

to:

or

It took me hours to understand what you mean, and I now understand how directly unconcealed was used, unconcealed is used as a synonym of unchanged.

PS. After hours of thinking, the only way I found to check every possible e and every possible m for this e. That's why I'll try to do it in C, but some other day.

oops - that's a pretty big typo on my part!!


But yeah, unconcealed = unhidden = unencrypted = unchanged.
 

·
Registered
Joined
·
1,198 Posts
Quote:


Originally Posted by Manyak
View Post

oops - that's a pretty big typo on my part!!


But yeah, unconcealed = unhidden = unencrypted = unchanged.

Here you go...

Language: C (gcc compiler with GMP library)

Code:
Code:
/**
 * RSA - Find strongest e,d pairs (p=1009, q=3643)
 * metala <Marin Ivanov> - Overclock.net
 *
 * LICENSE: Licensed under the terms of the GNU General Public License v2
 *          http://www.gnu.org/licenses/gpl-2.0.html 
 */

#include <stdio.h>
#include <gmp.h>

long int gcd(long int a, long int b)
{
   return ( b == 0 ? a : gcd(b, a % b) );
}

int main()
{
long int p = 1009;
long int q = 3643;
long int n = p*q;
long int f = (p-1)*(q-1);
printf("p = %dn", p);
printf("q = %dn", q);
printf("n = %dn", n);
printf("f = %dn", f);
printf("Press enter to dump e,d pairs with 9 possible unconcealed messages...");
getchar(); // Pause
long int e, cnt, d;
mpz_t mpd, mpe, mpf;
mpz_init(mpd); mpz_init(mpe); mpz_init(mpf);
mpz_set_si(mpf, f);
long int i = 0;
for (e = 2; e < f; e++){
if(gcd(e, f) == 1){
// Formula
// [1 + gcd(e − 1, p − 1)] · [1 + gcd(e − 1, q − 1)]
// END Formula
cnt = (1 + gcd(e-1, p-1))*(1 + gcd(e-1, q-1));
if (cnt == 9){ //cnt min is 9
i++;
//Find d
mpz_set_si(mpe, e);
mpz_invert(mpd, mpe, mpf);
d = mpz_get_si(mpd);
printf("e=%d, d=%d;n", e, d);
}
}
}
//printf("%dn", i); //217800
return 0;
}
It's limited, but for input parameters p=1009, q=3643, I don't think I need to use the full capacity of GMP library.

PS. about the gcd, I would have used the original one that is with the subtraction, but found modulo one and it sounds faster.
PS2. I found the formula with Google in a pdf book, Chapter 8
http://www.cacr.math.uwaterloo.ca/hac/
 

·
Registered
Joined
·
3,102 Posts
Now someone should do one in FORTRAN...
 

·
Registered
Joined
·
219 Posts
Towers of Hanoi with c++

^_^

Working on the rest. I can't think of how to beat the damn prime numbers problem.

Code:
Code:
//By Action Trey! on OCN.
#include <iostream>
#include <string>

using namespace std;

void moveDisks(int, string, string, string);

int main()
{
int num;

cout << "How many disks would you like to use in solving this game?n"
 << "(I would suggestion using 3 or 4, or you will get spammed with the answer)n";
cin >> num;

moveDisks(num, "peg 1", "peg 3", "peg 2");

cout << "...and you're done!nThat's the fastest way to beat the Towers of Hanoi!n";

system ("pause");
return 0;
}
//*****************************************************************
//The moveDisks function displays disk moves used to solve the
//Towers of Hanoi game. The parameters are:
// n      : The number of disks to move.
// source : The peg to move from.
// dest   : The peg to move to.
// temp   : The temporary peg.
//*****************************************************************

void moveDisks(int n, string source, string dest, string temp)
{
if( n > 0)
{
//Move n-1 disks from source to temp
//using dest as the temporary peg.
moveDisks(n - 1, source, temp, dest);

//Move a disk from source to dest.
cout << "Move a disk from " << source << " to " << dest <<endl;

//Move n-1 disks from temp to dest
//using source as the temporary peg.
moveDisks(n - 1, temp, dest, source);
}
}
 

·
Registered
Joined
·
219 Posts
I'm a little confused on your factorial sum question, could someone clarify it for me so i can figure out the correct algorithm?

i got this far before i realized i didn't know what he was asking.. haha

Code:
Code:
//By Action Trey! of OCN.
#include <iostream>
#include <iomanip>
using namespace std;

double factorial(double);

int main()
{
double number;

cout << "Enter an integer value and I will display it's factorial,n and the steps to determine it: n(Weird output on big numbers... =)";
cin >> number;

cout << "The factorial of " << number << " is:n";
cout << fixed << setprecision(0);
cout << factorial(number) << endl;

system ("pause");
return 0;
}

/******************************************************************************************************/

double factorial(double num)
{
if (num > 0)   //displays number everytime an instance of the factorial function is run
cout << " " << num ;

if (num == 0)              //base case
{
cout << " = ";       //displays the equal sign when the base case of the factorial function is met
return 1;
}
else
{ 
if (num > 1)           //displays the asterisk to represent multiplication for every number of the
cout << " * ";     //of the function that is being multipled in the next statement. A limit of >
   // then 1 must be put or an extra asterisk will be displayed.
return num * factorial(num - 1);
}

}

/******************************************************************************************************/
 

·
Registered
Joined
·
219 Posts
=P it starts on a monday, it makes it easy.
...i didn't think about this one tooo much if you didn't notice =P haha

Code:
Code:
//by Action Trey of OCN.
#include <iostream>
using namespace std;

int main()
{
int totalDays = 36525;   //total days in the 19th century
totalDays /=  7;
cout << " There were "<< totalDays << " Sundays in the 19th centuryn";

system ("pause");
return 0;
}
 

·
Registered
Joined
·
219 Posts
I was getting impatient waiting for anything over 40,000 to finish debugging.
=P

Code:

Code:
//by Action Trey! of OCN.
#include <iostream>
using namespace std;

int main()
{
int x = 40000;
int z = 0;

for(int y = 2; y < x; y)
{
y = y + 2;
z = (z + y);
cout << z << " ";
}

cout << "nnThe sum of all even numbers under 40,000 is: " << z << endl;
system ("pause");
return 0;
}
 

·
Premium Member
Joined
·
11,951 Posts
Discussion Starter · #31 ·
great work guys


^^That sum of even numbers is incorrect though. Follow the variables through the 1st loop:
y starts at 2
y becomes 4
z becomes 0+4

"2" is skipped!


a better loop would be:

Code:
Code:
int sum = 0;
for (int num = 0; num < 40000; num+=2)
{
sum+=num;
}
cout << sum;
 

·
Registered
Joined
·
1,198 Posts
I'll put a rough C code of the "Circular primes"

Code:
Code:
/**
 * Circular primes
 * metala <Marin Ivanov> - Overclock.net
 *
 * LICENSE: Licensed under the terms of the GNU General Public License v2
 *          http://www.gnu.org/licenses/gpl-2.0.html 
 */

#include <stdio.h>
#include <math.h>

int isPrime(int p)
{
if (p % 2 == 0) return 0;
int i, e = floor(sqrt(p));
for (i=3;i<e;i++){
if(p % i == 0) return 0;
}
return 1;
}
int combine(int a, int b, int c)
{
return 100*a+10*b+c;
}

int main()
{
int i, n1, n2, n3;
for(i=0;i<1000;i++){
n1 = i / 100;
n2 = (i /10) % 10;
n3 = i %10;
if (isPrime(i) && isPrime(combine(n2,n1,n3)) && isPrime(combine(n3, n2,n1))) printf("%d \
", i);
}
        return 0;
}
 

·
Premium Member
Joined
·
13,477 Posts
Hey, I ran that factorial one, and 145 was the only number that came up!
 

·
Premium Member
Joined
·
5,315 Posts
Fibonacci Sums:

Code:

Code:
/*Barnabas Sapan
2008.11.24
Fibonaccitalen

Efter avslutad loop byts Y mot X och X mot svar.

Y   X Svar
8 + 13 = 21

X      Svar  Nytt Svar
13  +   21   = 34

*/

#include <iostream>
using namespace std;

int main()
{
unsigned int svar = 0;
unsigned int y = 1;
unsigned int x = 0;
int input = 0;

cout << "Times to loop? ";
cin >> input;

for (int n = 0; n < input; n++)
{
svar = y + x;

if (n == 0)
{
cout << svar - 1 << endl;
continue;
}

cout << svar << endl;

y = x;
x = svar;

}

}
 

·
Premium Member
Joined
·
5,315 Posts
Primes:

EDIT: This does not calculate circular primes.

Code:

Code:
/*Barnabas Sapan
2008.11.26
Prime numbers

Kör helt enklet en brute force teknik för att hitta primes. Efter avlutad beräkning presenteras
tiden och antalet funna primes. Det finns säkert effektivare metoder som uteslutar vissa tal för snabbare
beräkningare, men har inte satt mig in i prims så mycket en. Kommer jag på en bättre ide updaterar jag
denna.
*/

#include <iostream>
#include <Windows.h>
using namespace std;

int checkForPrimes(int number, int times)
{
int p_number = number;
int p_times = times;
int p_isValid = 0;
int p_primeCount = 0;
int p_loop = 0;
float p_svarF = 0;
int p_svarI = 0;

while (p_loop < p_times)
{
p_number++;
p_loop++;
for (int i = 1; i < (p_number + 1); i++)
{
p_svarF = float(p_number) / i;
p_svarI = p_number / i;

if (p_svarF == p_svarI)
p_isValid++;
}

if (p_isValid == 2)
{
p_isValid = 0;
p_primeCount++;
}

else
p_isValid = 0;
}

return p_primeCount;
}

int main()
{
int size = 0;
cout << "Length: ";
cin >> size;

cout << "Starting stress test with current settingsn" << endl;

float startTime = float(GetTickCount());
int primes = checkForPrimes(0, size);
float endTime = float(GetTickCount());

float time = endTime - startTime;

cout << "Found " << primes << " primes in " << (time / 1000) << " sec.n" << endl;
system("pause");
}
 

·
Premium Member
Joined
·
2,687 Posts
Quote:


Originally Posted by timw4mail
View Post

Now someone should do one in FORTRAN...

You ask and I deliver. I think this is how to do the Fibonacci program in FORTRAN:

Code:
Code:
      PROGRAM FIB
      INTEGER A, B, SUM, TEMP
      A = 1
      B = 1
      SUM = 0
      DO 15, ITER = 1, 40000000
            TEMP = A
            A = B
            B = B + TEMP
            IF(MOD(B, 2) .EQ. 0)
                  SUM = SUM + B
            END IF
15    CONTINUE

      WRITE(*,*) SUM             
      END
It was not actually all that difficult for something this simple, other than it yelling at you the entire time.

Hmm, How about Verilog:

Code:
Code:
module Fibonacci;

integer a, b, sum, temp;
a = 1;
b = 1;
sum = 0;

repeat(40000000)
begin
      temp = a;
      a = b;
      b = b + temp;
      if((b % 2) == 0)
             sum = sum + b;
      endif
end

$display(sum);
endmodule
ARM assembly?


Code:
Code:
_start.
      MOV R0, #1                  @a
      MOV R1, #1                  @b 
      MOV R2, #0                  @sum, R3, R4 is temp
      MOV R5, #40000000     @number of repetitions

LOOP: MOV R3, R0
      MOV R0, R1
      ADD R1, R1, R3
      MOV R4, R1

EVEN: SUBS R4, R4, #2 
      BEQ BREAK
      BMI EVEN

BREAK: CMP R4, #0
      BNE IF

      ADD R2, R2, R1
IF:   SUBS R5, R5, #1
      BNE LOOP
Now I haven't actually tested any of these, but they should work.
 

·
Premium Member
Joined
·
11,951 Posts
Discussion Starter · #38 ·
Quote:


Originally Posted by Weedvender
View Post

How do you guy do these things!?
I can barely do this in math class.

believe it or not, programming them is actually easier than solving them on paper
 

·
Registered
Joined
·
821 Posts
Circular Primes in C++, built using a Test Driven Development approach:

Code:
Code:
#pragma once

#include "IStringRotator.h"

class StringRotator : public IStringRotator
{
public:
    StringRotator() {}

    virtual std::string Rotate(const std::string& str)
    {
        if (str.size() < 2)
            return str;
        const std::string firstChar = str.substr(0, 1);
        const std::string restOfString = str.substr(1);
        return restOfString + firstChar;
    }

    virtual std::vector<std::string> RotateForSizeOf(const std::string& str)
    {
        int rotations = (int)str.size() -1;
        if (rotations < 1)
            return std::vector<std::string>();

        std::string intermediate(str);
        std::vector<std::string> result;
        for (int i = 0; i < rotations; ++i)
            result.push_back(intermediate = Rotate(intermediate));
        return result;
    }

};
Code:
Code:
#pragma once

#include "IPrimalityTest.h"
#include <math.h>

class PrimeNumberValidator : public IPrimalityTest
{
public:
    PrimeNumberValidator() {}

    virtual bool IsPrimeNumber(int n)
    {
        if (n < 2)
            return false;
        double f = n + 0.0;
        int z, y = (int)sqrt(f);
        for (z = 2; z <= y; z++) 
        {
            if ((n % z) == 0)
                return false;
        }
        return true;
    }
};
Code:
Code:
#include "cppunit/extensions/HelperMacros.h"
#include "cppunit/TestFixture.h"
#include <stdio.h>

#include "OutputStream.h"
#include "StringRotator.h"
#include "PrimeNumberValidator.h"

class MockOutputStream : public IOutputStream
{
public:
    MockOutputStream() : m_counter(0) {}
    virtual void WriteLine(const std::string& line)
    {
        m_counter++;
        std::cout<< line << std::endl;
    }
    int m_counter;
    std::string m_output;
};

class CircularPrimesGenerator
{
public:
    CircularPrimesGenerator(IOutputStream* output, IStringRotator* rotator, IPrimalityTest* validator)
        : m_output(output), m_rotator(rotator), m_validator(validator)
    {
    }

    void Generate(int max)
    {
        for (int i = 0; i <= max; i++)
        {
            if (!m_validator->IsPrimeNumber(i))
                continue;
            char buf[16] = {0};
            std::vector<std::string> rotations = m_rotator->RotateForSizeOf(itoa(i, buf, 10));
            if (AllArePrimeNumbers(rotations))
                m_output->WriteLine(buf);
        }
    }

    bool AllArePrimeNumbers(std::vector<std::string> numbers)
    {
        if (numbers.size() == 0)
            return false;
        std::vector<std::string>::iterator it = numbers.begin();
        for (; it != numbers.end(); ++it)
        {
            int possiblePrime = atoi((*it).c_str());
            if (!m_validator->IsPrimeNumber(possiblePrime))
                return false;
        }
        return true;
    }

    virtual ~CircularPrimesGenerator()
    {
        delete m_output;
        delete m_rotator;
        delete m_validator;
    }

    IOutputStream* get_OutputStream() { return m_output; }
    IStringRotator* get_Rotator() { return m_rotator; }
    IPrimalityTest* get_Validator() { return m_validator; }

private:
    __declspec(property(get = get_OutputStream)) IOutputStream* OutputStream;
    IOutputStream* m_output;

    __declspec(property(get = get_Rotator)) IStringRotator* Rotator;
    IStringRotator* m_rotator;

    __declspec(property(get = get_Validator)) IPrimalityTest* Validator;
    IPrimalityTest* m_validator;

private:
    CircularPrimesGenerator(const CircularPrimesGenerator&);            // not implemented
    CircularPrimesGenerator& operator=(const CircularPrimesGenerator&); // not implemented
};

namespace UnitTests {
class CircularPrimesGeneratorTests : public CppUnit::TestFixture
{
    CPPUNIT_TEST_SUITE( CircularPrimesGeneratorTests );
    CPPUNIT_TEST( Ctor );
    CPPUNIT_TEST( Generate );
    CPPUNIT_TEST_SUITE_END();
public:
    CircularPrimesGeneratorTests() {}

    void Ctor() 
    {
        CircularPrimesGenerator generator(new OutputStream("results.txt"),
                                            new StringRotator,
                                            new PrimeNumberValidator);
        CPPUNIT_ASSERT(generator.OutputStream);
        CPPUNIT_ASSERT(generator.Rotator);
        CPPUNIT_ASSERT(generator.Validator);
    }

    void Generate() 
    {
        MockOutputStream* output = new MockOutputStream;;
        CircularPrimesGenerator generator(output,
                                            new StringRotator,
                                            new PrimeNumberValidator);
        generator.Generate(1000000);
        CPPUNIT_ASSERT(output->m_counter == 51);

    }

};
CPPUNIT_TEST_SUITE_REGISTRATION(CircularPrimesGeneratorTests);

}
51 of them...

Code:
Code:
11
13
17
31
37
71
73
79
97
113
131
197
199
311
337
373
719
733
919
971
991
1193
1931
3119
3779
7793
7937
9311
9377
11939
19391
19937
37199
39119
71993
91193
93719
93911
99371
193939
199933
319993
331999
391939
393919
919393
933199
939193
939391
993319
999331
 
21 - 40 of 99 Posts
Top