Is there a cleaner way to find p*q = n, when p and q are coprime?
Basically trying to write a simple RSA brute force. I have modulus N and I'm trying to find p*q=n where p and q are coprimes.
So far i'm able to find the prime factors of N and I can put them in a list. Then taking that list apart into variables then going through each pair to find coprimes. It's messy, and was wondering if there was a cleaner way of doing it?
my code so far:
from fractions import gcd
import sys
n= 17
print "Modulus (n) = ", n
print("p & q are:")
# While Loop to find prime factors
i=1
list=[]
while(i<=n):
k=0
if(n%i==0):
j=1
while(j<=i):
if(i%j==0):
k=k+1
j=j+1
if(k==2):
list.append(i)
i=i+1
# takes list of prime factors and splits to variables
for n, val in enumerate(list):
globals()["var%d"%n] = val
# really messy, tries to multiply first 2 variables, if coprime, print the variables
# if no coprime factors move on to next 2 variables
# if no prime factors in the first place, exit
try:
gg0 = gcd(var0,var1)
except:
print "No Prime Factors"
sys.exit()
try:
gg1 = gcd(var1,var2)
if gg1 == True:
print var1, var2
except:
if gg0 == True:
print var0, var1
See also questions close to this topic

Cant get a Sprite to be my avatar in my Basic Game
Ok i am creating a basic game at the moment where the user controls the sprite, i have looked online but all the solutions i found did not work and so i am coming here, i am creating this game on python.
The file is called Sprite.png
Thanks.
Here is my Code before trying to make the sprite my sprite:
import pygame import random BLACK = ( 0, 0, 0) WHITE = (255, 255, 255) RED = (255, 0, 0) class Block(pygame.sprite.Sprite): def __init__(self, color, width, height): super().__init__() self.image = pygame.Surface([width, height]) self.image.fill(color) self.rect = self.image.get_rect() pygame.init() screen_width = 700 screen_height = 400 screen = pygame.display.set_mode([screen_width, screen_height]) block_list = pygame.sprite.Group() all_sprites_list = pygame.sprite.Group() for i in range(50): block = Block(BLACK, 20, 15) block.rect.x = random.randrange(screen_width) block.rect.y = random.randrange(screen_height) block_list.add(block) all_sprites_list.add(block) player = Block(RED, 20, 15) all_sprites_list.add(player) done = False clock = pygame.time.Clock() score = 0 while not done: for event in pygame.event.get(): if event.type == pygame.QUIT: done = True screen.fill(WHITE) pos = pygame.mouse.get_pos() player.rect.x = pos[0] player.rect.y = pos[1] blocks_hit_list = pygame.sprite.spritecollide(player, block_list, True) for block in blocks_hit_list: score += 1 print(score) all_sprites_list.draw(screen) pygame.display.flip() clock.tick(60) pygame.quit()
I would also like some advice on how i can set my background to an image aswell thank you.

missing 1 required positional argument, Python code
I'm working on the python code for my class, and keep getting errors. I've tried everything I can think of and I'm not sure where my code is wrong at. My code is:
class Student: def t(self, m1, m2, m3): tot = m1 + m2 + m3 average = tot / 3 return average class Grade(Student): def gr(self, av): if av > 90: print('A grade') elif (av < 90) and (av > 70): print('B grade') elif (av < 70) and (av > 50): print('C grade') else: print('No grade') print("Grade System!") s = Student repeat = 'y' while repeat == 'y': a = input('Enter 1st subject Mark:') b = input('Enter 2nd subject Mark:') c = input('Enter 3rd subject Mark:') aver = s.t(a, b, c) g = Grade() g.gr(aver) repeat = input("Do you want to repeat y/n=")
And my error is:
Traceback (most recent call last): File "C:/PythonProjects/lab6/lab6.py", line 27, in <module> average = s.t(a, b, c) File "C:/PythonProjects/lab6/lab6.py", line 4, in t average = tot / 3 TypeError: unsupported operand type(s) for /: 'str' and 'int'
Any help or clues are appreciated.

Having interpreting this line in Python , where a conditional comes after a range specification.
I having trouble interpreting
indexes =[ s.index(l) for l in letters if s.count(l) == 1]
from the code belowclass Solution: def firstUniqChar(self, s): """ :type s: str :rtype: int """ letters = 'abcdefghijklmnopqrstuvwxyz' indexes =[ s.index(l) for l in letters if s.count(l) == 1] return min(indexes) if len(indexes) > 0 else 1
It looks like it's going through string s and if a letter from letts is in the string s, it records where that index position is. Then it returns only indexes if the count for that index is equel to 1. But I tried to run the code without the conditional in that line
indexes =[ s.index(l) for l in letters ]
and it returns an error
'ValueError: substring not found'
Here is what I use to instatiate and run the function
sol = Solution() sol.firstUniqChar('loveleetcode')

custom List constructor resulting in 'List and scala.collection.immutable.List ' conflict
I am new to scala. be gentle. I think the problem is that I created a Trait List which conflicts with scala.collection.immutable.List
trait List[T] { def isEmpty: Boolean def head[T] def tail[T] } class Cons[T](val head:T, val tail: Option[List[T]]) extends List[T] { def isEmpty: Boolean = false def head[T] = head def tail[T] = tail } class Nil[T] extends List[T] { def isEmpty: Boolean = true def head[T] = throw new IllegalStateException("head") def tail[T] = throw new IllegalStateException("tail") } // ERROR HERE // obj with one elem val one: Cons[Int] = new Cons[Int](1,Option(scala.List[Int]()))
the error is: expected scala.Option[List[Int]], actual scala.Option[scala.collection.immutable.List[Int]]
Thank you.

Changing python string in a list
I’m trying to replace part of a string from within a list So far I have this code:
newName = 'MeshNew' list = ['mesh.vtx{12}' 'mesh.vtx{13}'] #print(list) for i in (list): new = i.split('mesh.vtx') print(new)
I need it to print out
MeshNew.vtx{12},MeshNew.vtx{13}
What would be the solution here?

ArrayList speed issue
I've been working on a voxel engine and I've run into an issue. Basically when I built a chunk, I add the vertices, normals, and texture coordinates to lists (since I don't know how many there will be yet), those then get converted to arrays and stored in VBOs for rendering. This works fine and is pretty fast. The issue is, until this point I hadn't been worrying about normals, now that I add normals it went from 12MS to add everything to the lists to 30+ MS! And even weirder there is a clear point where this happens. For example lets say I only add 20 normals, it runs fine, but if I add 21 it slows way down. It makes no sense to me... Any help is appreciated!

Do I have to generate two RSA keys for a server client connection?
I created a TCP ChatServer in C# with an loginsystem, but i don't know how i have to encrypt messages. My idea is to send to all clients different public keys and from the side of the clients a new public key to the server, so that both sides can send encrypted messages.
Is this an option or do I have some safety problems here?

PKCS7 encryption usnig java6 and no external libraries
I need to call a webservice which needs pkcs7 encoded xml in the request header. I cannot use BouncyCastle or any other external library. I can only use java 6 provided libraries.
I am using below code to encrypt using SUN Security.
import java.io.ByteArrayOutputStream; import java.io.FileInputStream; import java.io.StringWriter; import java.math.BigInteger; import java.security.KeyPair; import java.security.KeyPairGenerator; import java.security.KeyStore; import java.security.MessageDigest; import java.security.NoSuchAlgorithmException; import java.security.PrivateKey; import java.security.PublicKey; import java.security.Signature; import java.security.cert.CertificateEncodingException; import java.security.cert.CertificateFactory; import java.security.cert.X509Certificate; import javax.xml.bind.DatatypeConverter; import javax.xml.bind.JAXBContext; import javax.xml.bind.JAXBException; import javax.xml.bind.Marshaller; import org.apache.commons.codec.binary.Base64; import sun.security.pkcs.ContentInfo; import sun.security.pkcs.PKCS7; import sun.security.pkcs.SignerInfo; import com.ibm.security.util.DerOutputStream; import com.ibm.security.util.DerValue; import com.ibm.security.x509.AlgorithmId; import com.ibm.security.x509.X500Name; public class PKCS7EncryptionM { public static void main(String[] args) throws Exception { final String STORENAME = "pathToKeysStore/trust.p12"; final String STOREPASS = "WebAS"; //First load the keystore object by providing the p12 file path KeyStore clientStore = KeyStore.getInstance("PKCS12"); //replace testPass with the p12 password/pin clientStore.load(new FileInputStream(STORENAME), STOREPASS.toCharArray()); CertificateFactory certFactory = CertificateFactory.getInstance("X.509"); X509Certificate certificate = (X509Certificate) certFactory.generateCertificate(new FileInputStream( "/root/Desktop/PublicCertificate.cer")); String thumbprint = getThumbprint(certificate); System.out.println("thumbprint "+ thumbprint); // Data to sign byte[] dataToSign = createXmlPayload().getBytes("UTF8"); // load X500Name X500Name xName = new X500Name(certificate.getIssuerX500Principal() .getName()); // Generating private/public key for digitally signing the data. KeyPairGenerator keyGen = KeyPairGenerator.getInstance("RSA"); keyGen.initialize(2048); KeyPair pair = keyGen.generateKeyPair(); PrivateKey privKey = pair.getPrivate(); PublicKey publicKey = pair.getPublic(); //compute signature: Signature signature = Signature.getInstance("Sha1WithRSA"); signature.initSign(privKey); signature.update(dataToSign); byte[] signedData = signature.sign(); // load serial number BigInteger serial = certificate.getSerialNumber(); // load digest algorithm AlgorithmId digestAlgorithmId = new AlgorithmId(AlgorithmId.SHA_oid); // load signing algorithm AlgorithmId signAlgorithmId = new AlgorithmId( AlgorithmId.RSAEncryption_oid); SignerInfo sInfo = new SignerInfo(xName, serial, digestAlgorithmId, signAlgorithmId, signedData); ContentInfo cInfo = new ContentInfo(ContentInfo.DIGESTED_DATA_OID, new DerValue(DerValue.tag_OctetString, dataToSign)); PKCS7 p7 = new PKCS7(new AlgorithmId[] { digestAlgorithmId }, cInfo, new java.security.cert.X509Certificate[] { certificate }, new SignerInfo[] { sInfo }); // Write PKCS7 to bYteArray ByteArrayOutputStream bOut = new DerOutputStream(); p7.encodeSignedData(bOut); byte[] encodedPKCS7 = bOut.toByteArray(); System.out.println("the encoded strinh  " + new String(encodedPKCS7)); System.out.println("base 64 the encoded strinh  " + new String(Base64.encodeBase64(encodedPKCS7))); } private static String createXmlPayload() { Ebidenws giftCardReq = new Ebidenws(); // This xml needs to be encrypted using pkcs7. String xmlString = "<ebid pc_id="TKGN" version="0100"><abi>064444</abi> <certificato>asdfasdf</certificato></ebid>"; return xmlString; }
}
Output:(I am getting exactly same string in encoded string, which i think, is not correct)
[Image is the encrypted text]
The encrypted text i am getting seems not correct. Could any one confirm how to correctly encode using pkcs7?
I tried to decode the encoded string using bouncyCaslte as i cannot find anything in java6 libraries to decode. i am getting error while deocoding 'malformed contents'(reason could be that the encoding is not correct.)
Any suggestions are apreciated.

Why use `t rsa b 4096` with sshkeygen?
Why should I use the options,
t rsa
,b 4096
, andC "myemail@example.com"
when creating an SSH key, as instructed by github? If I create an SSH key without these options, is it less secure? If so, why?What frustrates me about these options is that they're hard to remember (is it 4096 or 4095? Which flag went with the number and which went with the "rsa" value? Which flag went in front of my email? Wasn't it an uppercase letter?), and creating new keys can be a frequent activity, for example, if trying out bitbucket and gitlab, and different cloud hosting providers.

How to calculate the product from combinations of several vectors in R?
I feel it hard to give an accurate title, though I have tried my best. Here's my problem.
a = 1/(1:10) b = 3/(1:10) c = 1/(1:5) d = 1/(1:11)
I would like to get a vector
e
, such thate
consists of the product calculated from the combinations of values chosen froma
,b
,c
andd
.For example, supposing there are two vectors
{1, 2}
and{3, 4}
, I would like to get a vector like this{1 * 3, 1 * 4, 2 * 3, 2 * 4} = {3, 4, 6, 8}
.Thanks in advance!

Multiplication table, ask until all correct answers are made
I have a program that will help the user to learn a multiplication table and then show results of right/wrong answers. The first step is to simply ask the user for which multiplication table it want to work on (19). And then the user will get a random sequence of number multiplied by the chosen multiplication table. If the user answers correctly then that number won't be shown again, but if incorrectly then it will be shown until the correct answer is made.
One scenario could be that the user chooses "3", and it will then be displayed in a random sequence such as (3x7 =, 3x1 =, 3x9 =...). And the user will answer after each "=". Right now, I can only print it all in ascending order, should I use Random multiplied with the chosen table in a while loop instead?.
My second issue, is how I can ask the incorrectly answered numbers again, until correctly answered? Am I right to think that a for loop isn't the best choice in this case?
Here is my code so far:
public class Multiplication { public static void main (String[] args) { Scanner inread = new Scanner (System.in); int answer; System.out.println("Choose multiplication table (19)"); int num1= inread.nextInt(); for (int i=1; i<11; i++) { System.out.println("Write answer after = "); System.out.println(num1 + " x " + (i) + " = "); answer=inread.nextInt(); if (answer == (num1 * i) ) { System.out.println("Correct answer"); // Do not show that number again } else { System.err.println("Wrong answer"); //Show this number again. } } } }
New code after int num1 = inread.nextInt();
unanswered.add(1); unanswered.add(2); unanswered.add(3); unanswered.add(4); unanswered.add(5); unanswered.add(6); unanswered.add(7); unanswered.add(8); unanswered.add(9); unanswered.add(10); Collections.shuffle(unanswered); while (!unanswered.isEmpty()) { System.out.println(num1 + "*" + "unanswered" + " = "); //? answer = inread.nextInt(); if (answer == (num1 * unanswered)) { //? unanswered.remove(unanswered); //? } }
So, I think this is almost the way you suggested? However I'm sure I could add the numbers in a more beautiful way. I am used to looping through lists with a for loop in order to then use the counter to display the list. So where I putted a "?" is because I am not sure how to specify where in the list I am trying, for example to remove a number.
Or should I have the while loop, inside the for loop that I originally had? So that I could use the (i) in the for loop to specify where in the list I will display and perhaps remove?

Why does this array in C keeps assigning garbage value to itself?
I have been trying this popular question, where I have to multiply two very large numbers in C (without using any libraries other than stdio.h). I know my algorithm and code are correct, since it works on dry runs.
However, the ans array here keeps allocating itself garbage value, to which I cannot find any reason whatsoever.
The input format is number1 * number2
Following is my code:
#include <stdio.h> int main(){ char str[200]; gets(str); int length = 0; for (int i = 0; ; i++){ if(str[i]=='\0'){ break; } length++; } int s1[101], s2[101]; int l1 = 0, l2 = 0, temp = 0; for(int i = 0; i<length; i++){ l1++; if(str[i]=='*'){ l1=2; temp = i; break; } } l2 = lengthl1; l2=3; for(int i = 0; i<l1; i++){ s1[i] = str[i]'0'; } for(int i = l1+3; i<length; i++){ s2[i] = str[i]'0'; } int a[100],b[100]; int ans[200]; int i,j,tmp; for(int k = 0; i<200; i++){ ans[k] = 0; } j = l1  1; i = 0; while (i < j){ tmp = s1[i]; s1[i] = s1[j]; s1[j] = tmp; i++; j; } j = l2  1; i = 0; while (i < j){ tmp = s2[i]; s2[i] = s2[j]; s2[j] = tmp; i++; j; } for(i = 0;i < l2;i++){ for(j = 0;j < l1;j++){ ans[i+j] += s2[i]*s1[j]; printf(" %d", ans[i+j]); } } for(i = 0;i < l1+l2;i++) { tmp = ans[i]/10; ans[i] = ans[i]%10; ans[i+1] = ans[i+1] + tmp; } for(i = l1+l2; i>= 0;i) { if(ans[i] > 0) break; } //printf("Product : "); for(;i >= 0;i) { //printf("%d",ans[i]); } return 0; }
Can anyone help me out with this problem and tell me why this garbage value comes, and how to avoid this error?

Unexpected error in the result when implementing an algorithm from The Art of Computer Programming
Algorithm C on page 387 of volume 2 describes a method to find the largest factor of N less than or equal to sqrt(N) which I implemented in C as follows (Why  because I felt like it, this isn't a homework assignment!):
int test(int N) { long a, b, s, r, m, x, y; /* Given an odd number N, find the largest factor of N less than or * equal to sqrt(N). (Algorithm C on page 387 of "The Art of Computer * Programming" volume 2) */ s = (int) sqrt(N); a = 2 * s + 1; b = 1; r = (s * s)  N; while (r != 0) { r += a; a += 2; do { r = b; b += 2; } while (r > 0); } x = (a  b) / 2; y = (a + b  2) / 2; /* Should be less than or equal to sqrt(N) */ return (y); }
However for some values this code doesn't work  for example when N = 99999 the value returned is 369 which is not right as the largest factor of 99999 which is less than sqrt(99999) is actually 271.
However for N = 369 then the value returned is 41 which is correct.
What have I missed? I've checked for errata and incorporated the only known correction to Algorithm C in my in my code.

prime factorization with large numbers in python
whazzup,
Having the following problem, I can't get it fixed. Handling with numbers having a length around 5  52, I wan't to get their prime factors. Using Python, I found the following two algorithms:
I.
def faktorisiere(n): l = [] # Lösungsmenge # Auf Teilbarkeit durch 2, und alle ungeraden Zahlen von 3..n/2 testen for i in chain([2], range(3, n//2 + 1, 2)): # Ein Teiler kann mehrfach vorkommen (z.B. 4 = 2 * 2), deswegen: while n % i == 0: l.append(i) print(i) n = n // i # "//" ist ganzzahlige Division und entspricht int(n/i) if i > n: # Alle Teiler gefunden? Dann Abbruch. break print(l)
II.
x = input("Number: ") mode = x[1:] x = int(x[:1]) if int(x) < 1000000000000: faktorisiere(x) else: if mode == 'f': faktorisiere(x) rx = int(sqrt(x)) + 1 for i in range(1, rx+1): if mode == 'a': if x % i == 0: y = int(x/i) print(str(x), "=", i, "*", str(y)) if mode == 'u': if i % 2 != 0: if x % i == 0: y = int(x/i) print(str(x), "=", i, "*", str(y))
But the first code is very slow computing numbers like these: 1917141215419419171412154194191714
The second is working a little faster, but I get wrong outputs and I can't find the mistake in code. As an example we take the given number. These are the first lines of pythons output:
1917141215419419171412154194191714 = 1 * 1917141215419419143900621852114944
1917141215419419171412154194191714 = 2 * 958570607709709571950310926057472
 1917141215419419171412154194191714 = 3 * 639047071806473023947675938062336
But as you can see, these multiplications don't equal the result. Is there any mistake in the code? Or is it just because of the length of numbers? Hope you can help me.
Best wishes, TimeMen

Yun's algorithm
I would like to try to implement Yun's algorithm for squarefree factorization of polynomials. From Wikipedia (
f
is the polynomial):a0 = gcd(f, f'); b1 = f/a0; c1 = f'/a0; d1 = c1  b1'; i = 1 repeat ai = gcd(bi, di); bi+1 = bi/ai; ci+1 = di/ai; i = i + 1; di = ci  bi' until b = 1
However, I'm not sure about the second step. I would like to use it for polynomials with integer coefficients (not necessary monic or primitive). Is it possible to realize the division
b1 = f/a0
using just integers?I found the code for synthetic division:
def extended_synthetic_division(dividend, divisor): '''Fast polynomial division by using Extended Synthetic Division. Also works with nonmonic polynomials.''' # dividend and divisor are both polynomials, which are here simply lists of coefficients. Eg: x^2 + 3x + 5 will be represented as [1, 3, 5] out = list(dividend) # Copy the dividend normalizer = divisor[0] for i in xrange(len(dividend)(len(divisor)1)): out[i] /= normalizer # for general polynomial division (when polynomials are nonmonic), # we need to normalize by dividing the coefficient with the divisor's first coefficient coef = out[i] if coef != 0: # useless to multiply if coef is 0 for j in xrange(1, len(divisor)): # in synthetic division, we always skip the first coefficient of the divisor, # because it is only used to normalize the dividend coefficients out[i + j] += divisor[j] * coef # The resulting out contains both the quotient and the remainder, the remainder being the size of the divisor (the remainder # has necessarily the same degree as the divisor since it is what we couldn't divide from the dividend), so we compute the index # where this separation is, and return the quotient and remainder. separator = (len(divisor)1) return out[:separator], out[separator:] # return quotient, remainder.
The problem for me is that
out[i] /= normalizer
. Would it always work with integer (floor) division for Yun'sb1 = f/a0
? Is it so that it is always possible to dividef/gcd(f, f')
? Is theout[separator:]
(remainder) always going to zero?